LeetCode 869. Reordered Power of 2

If you prefer a quick walk through:

You are given an integer n. We reorder the digits in any order (including the original order) such that the leading digit is not zero.

Return true if and only if we can do this so that the resulting number is a power of two.

Example 1:

Input: n = 1
Output: true

Example 2:

Input: n = 10
Output: false

Constraints:

• 1 <= n <= 109

Problem Link: https://leetcode.com/problems/reordered-power-of-2/

Intuition

We know that in this question, the input n is less and equal to 10⁹ so the powers of 2 can be 1, 2, 4, and 8 all the way up to 2 to the power of 29 since 2²⁹ is less than 10⁹ and 10⁹ is less than 2³⁰.

Since We can reorder the digits in any order, input 218 can be reordered into 128 which is 2 to the power of 7. On the other hand, input 123 returns false since all the combinations of 123 [213, 123, 132, 231, 213, 312, 321] are not the power of 2.

The observation we can make is that reordering digits of a number in any order does not change the number of occurrences of its digits. So the main idea behind solving this question is that we want to count the occurrence of each digit in the input N and compare it with the occurrence of each digit in the powers of 2. If the occurrences are the same, it means that we can reorder the digits of N to have the resulting number as a power of 2. If the occurrence is not the same, it means we can’t reorder the digits to become a power of 2.

If we consider the previous example, 218 returns true since 218 and 128 = 2⁷ both have one 1, one 2, and one 8. 123 returns false since it does not match any powers of 2.

Approach

First, we need to understand the counter method. The counter method is a class from the collections module in Python, which is used to count the occurrences of elements. In this case, we will use it to count the occurrences of each digit in a number.

We start by converting the given number N to a string and then using the counter method to count the occurrences of each digit in N. We use the variable occurrence to store the result.
Next, we will use a for loop to iterate through the range of 0 to 29. In each iteration, we compare the occurrence of each digit in 2 to the power of i to the occurrences of each digit of the given number N. if they are the same, we return True, otherwise, we increment i and keep comparing.
If the loop completes and no match is found, it means the digits of N cannot be reordered to form a power of 2, we return False.

class Solution(object):
    def reorderedPowerOf2(self, n):
        """
        :type n: int
        :rtype: bool
        """
        occurrence = Counter(str(n))
        for i in range(30):
            if (occurrence == Counter(str(2**i))):
                return True
        return False

Follow our Youtube channel for new updates:

https://www.youtube.com/@algo.monster

AlgoMonster focuses on both learning and practice. You get everything you need to excel at your technical interviews: a detailed introduction to the key coding patterns, examples and problems, presented in a highly visual and interactive environment. Follow our website for more information:

https://algo.monster/