Reordered Power of 2

Reordered Power of 2

What is this problem about?

The Reordered Power of 2 interview question asks whether you can rearrange the digits of a given positive integer n (in any order, without leading zeros) to form a power of 2. If any permutation of n's digits equals a power of 2, return true; otherwise, return false. This is a digit counting and enumeration problem.

Why is this asked in interviews?

This problem is asked at Microsoft, Meta, Amazon, and Bloomberg because it tests creative problem reduction. Instead of generating all permutations (factorial time), a smart candidate recognizes that two numbers are digit-permutations of each other if and only if their sorted digit strings (or digit frequency counts) are identical. This reduces the problem to comparing sorted digits of n against sorted digits of all powers of 2 up to the maximum possible value.

Algorithmic pattern used

The pattern is digit counting with enumeration. Precompute the digit signature (sorted digits as a tuple or string) of every power of 2 that has the same number of digits as n. Since 2^0 through 2^29 cover all integers up to 10^9, the set is small. Sort the digits of n and check if any power of 2 in the valid range has the same sorted-digit signature. Using a hash table of precomputed sorted-digit signatures allows O(1) lookup.

Example explanation

n = 46. Sorted digits of 46: "46".

Powers of 2 with 2 digits: 16, 32, 64.

• Sorted digits of 16: "16".
• Sorted digits of 32: "23".
• Sorted digits of 64: "46" ✓ Match!

Return true (because 46 can be rearranged to 64 = 2^6).

n = 10. Sorted digits: "01". Powers of 2 with 2 digits: 16("16"), 32("23"), 64("46"). No match. Return false.

Common mistakes candidates make

• Generating all digit permutations explicitly — this is O(d!) where d is the number of digits, completely unnecessary.
• Not filtering powers of 2 by digit count — comparing digit counts of different lengths will never match.
• Forgetting that leading zeros are not allowed — this is naturally handled since powers of 2 never start with 0.
• Not covering all powers of 2 up to the constraint limit (10^9 requires up to 2^30).

Interview preparation tip

For the Reordered Power of 2 coding problem, the hash table, counting, and enumeration interview pattern is the elegant approach. Precompute all valid power-of-2 digit signatures at the start. The math and enumeration insight — use sorted digits as a canonical form — is the core skill. Interviewers at Bloomberg and Meta appreciate when you articulate this reduction explicitly: "Two numbers are digit-permutations iff their sorted digit strings are equal." State this before coding.