How do you solve Reordered Power of 2 on LeetCode?

Reordered Power of 2 (LeetCode #869) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: Powers of two have unique digit patterns.

What is the brute force solution for Reordered Power of 2?

The brute force approach for Reordered Power of 2 is Brute Force, with O(n!) time complexity and O(n) space complexity. The brute force approach involves generating all possible permutations of the digits of the number and checking if any of them form a power of two. This is straightforward but inefficient due to the factorial growth of permutations. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve Reordered Power of 2?

Reordered Power of 2 uses the following concepts: Hash Table, Math, Sorting, Counting, Enumeration. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Reordered Power of 2?

Explain your thought process clearly. Discuss edge cases like single-digit numbers. Consider both time and space complexity in your solution.

What are common mistakes when solving Reordered Power of 2?

Not considering leading zeros in permutations. Overlooking the range of powers of two.

#869

Reordered Power of 2

Medium

Hash TableMathSortingCountingEnumerationHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n!)	O(n log n)
Space	O(n)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

Instead of generating permutations, we can precompute all powers of two up to 2^30 and compare the sorted digit representation of the input number with these precomputed values. This is much more efficient.

⚙️

Algorithm

3 steps

1Step 1: Precompute all powers of two from 2^0 to 2^29 and store their sorted digit representations.
2Step 2: Convert the input number n into a sorted string of its digits.
3Step 3: Check if the sorted digit representation of n matches any of the precomputed powers of two.

solution.py6 lines

1# Full working Python code
2import itertools
3
4def reorderedPowerOf2(n):
5    powers_of_two = sorted([''.join(sorted(str(1 << i))) for i in range(30)])
6    return ''.join(sorted(str(n))) in powers_of_two

ℹ

Complexity note: The time complexity is O(n log n) due to sorting the digits of n, and the space complexity is O(n) for storing the sorted representations of powers of two.

1Powers of two have unique digit patterns.
2Sorting is a powerful tool for comparison.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.