Reordered Power Of 2 - Leetcode Solution

The Reordered Power of 2 problem on LeetCode is a problem that asks you to determine if there exists a power of two such that its digits can be rearranged to form a given number.

The problem statement can be summarised as follows:

Given a positive integer n, return true if there exists a power of 2 such that its digits can be rearranged to form n, or false otherwise.

To solve this problem, we first need to understand what it means for a number to be a power of two. A number is a power of two if and only if its binary representation contains only one 1 digit. For example, 2 (10 in binary), 4 (100 in binary) and 8 (1000 in binary) are all powers of two.

With this in mind, our approach to solving the problem will be as follows:

1. We first count the number of digits in the given number n.
2. We then generate all possible power of two numbers with the same number of digits as n.
3. For each generated power of two number, we check if its digits can be rearranged to form n.

Let's take a closer look at each of these steps.

Step 1: Count the number of digits in n

To count the number of digits in n, we can simply convert it to a string and count the number of characters in the string.

Example: n = 123 Number of digits = 3

Step 2: Generate all possible power of two numbers with the same number of digits as n

To generate all possible power of two numbers with the same number of digits as n, we can start by finding the lowest and highest power of two numbers that have the same number of digits as n.

We can find the lowest and highest power of two numbers by starting with 2^0 (which is 1) and multiplying it by 2 until we get a number with the same number of digits as n. The lowest power of two number will be the last power of two number that we multiplied by 2 before we got a number with the same number of digits as n. The highest power of two number will be the last power of two number that we multiplied by 2.

For example, if n has 4 digits, the lowest power of two number with 4 digits is 2^3 (which is 8) and the highest power of two number with 4 digits is 2^15 (which is 32768).

Once we have the lowest and highest power of two numbers, we can generate all power of two numbers between them and check if their digits can be rearranged to form n.

To generate all power of two numbers between the lowest and highest power of two numbers, we can start with the lowest power of two number and multiply it by 2 until we reach the highest power of two number.

Example: n = 123 Number of digits = 3 Lowest power of two number with 3 digits = 2^6 = 64 Highest power of two number with 3 digits = 2^7 - 1 = 127 All power of two numbers with 3 digits = [64, 68, 72, ..., 126, 127]

Step 3: Check if the digits of each power of two number can be rearranged to form n

To check if the digits of a power of two number can be rearranged to form n, we first convert both the power of two number and n to strings and sort the characters in both strings. If the sorted strings are equal, then the digits of the power of two number can be rearranged to form n.

Example: n = 123 Number of digits = 3 All power of two numbers with 3 digits = [64, 68, 72, ..., 126, 127] Power of two number to check = 72 Sorted string of power of two number = '27' Sorted string of n = '123' Result = false (sorted strings are not equal)

Putting it all together in code, we get:

class Solution: def reorderedPowerOf2(self, n: int) -> bool: # Count the number of digits in n num_digits = len(str(n))

    # Generate the lowest and highest power of two numbers with the same number of digits as n
    l = 2 ** (num_digits - 1)
    h = (2 ** num_digits) - 1
    
    # Generate all power of two numbers with the same number of digits as n
    powers_of_two = []
    for i in range(l, h + 1):
        if bin(i).count('1') == 1:
            powers_of_two.append(i)
    
    # Check if the digits of each power of two number can be rearranged to form n
    for power in powers_of_two:
        if sorted(str(power)) == sorted(str(n)):
            return True
    
    return False

This code first counts the number of digits in n, then generates the lowest and highest power of two numbers with the same number of digits as n, and finally generates all power of two numbers between the lowest and highest power of two numbers and checks if their digits can be rearranged to form n.

Note that we check if a number is a power of two by counting the number of 1 digits in its binary representation using the count() method. Also note that we sort the characters in the strings using the sorted() function before comparing them.

The time complexity of this solution is O(2^d log d), where d is the number of digits in n. This is because we generate all possible power of two numbers with d digits and sort the characters in two strings (which takes log d time). The space complexity is O(2^d), which is the size of the powers_of_two list.

1