We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Reordered Power of 2

Number: 900

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an integer n, determine if its digits can be reordered (without leading zeros) to form a number that is a power of two. Return true if such a reordering exists, and false otherwise.

Key Insights

  • The problem reduces to comparing the digit frequency of the given number with those of powers of two.
  • Since reordering digits does not affect the frequency count, sort the digits of n and compare with the sorted digits of every valid power of two.
  • The range of n (1 <= n <= 10^9) implies that the number of digits is limited, so there are only a constant number of candidate powers-of-two to check.
  • Precompute the sorted representations of relevant powers of two and use a hash-based lookup for constant time checking.

Space and Time Complexity

Time Complexity: O(1) – Only a fixed number of candidate powers-of-two are processed (at most 30) along with sorting digits which takes O(d log d) with d being number of digits. Space Complexity: O(1) – Only constant extra space is used for storing the candidate signatures.

Solution

The solution uses the following approach:

  1. Convert the input integer n to a string and sort its digits.
  2. Precompute a list (or set) of sorted digit strings for each power of two that could possibly match the number of digits in n. Since n is at most 10^9, consider powers of two that have up to 10 digits.
  3. Check if the sorted digits of n exists in the precomputed set.
  4. Return true if a match is found and false otherwise.

The key insight is that if two numbers are permutations of each other, their sorted strings will be identical. This allows us to reduce the problem to simple string comparisons without trying all permutations.

Code Solutions

# Python solution for Reordered Power of 2

def reorderedPowerOf2(n: int) -> bool:
    # Convert the integer to a sorted string of its digits.
    sorted_n = sorted(str(n))
    # Iterate over possible powers of two.
    power = 1
    while len(str(power)) <= len(str(n)):
        # Check if the sorted digits of the current power matches.
        if sorted(str(power)) == sorted_n:
            return True
        power *= 2
    return False

# Example usage:
print(reorderedPowerOf2(1))  # Output: True
print(reorderedPowerOf2(10))  # Output: False
← Back to All Questions