Reordered Power of 2 - Video Solutions

Problem Overview: Given an integer n, determine whether you can reorder its digits so the resulting number becomes a power of two. The reordered number cannot have leading zeros. The core challenge is verifying whether any permutation of the digits matches the digits of a valid power of two.

Approach 1: Backtracking Permutations (O(d! * d) time, O(d) space)

This approach generates every permutation of the digits of n using backtracking. For each permutation, skip cases where the first digit is 0 to avoid leading zeros. Convert the permutation to a number and check whether it is a power of two using the bit trick x & (x - 1) == 0. The algorithm explores the full permutation tree, which leads to factorial complexity O(d!) where d is the number of digits. Space usage is O(d) for recursion and the permutation path. This method is straightforward and demonstrates brute‑force reasoning, but it becomes inefficient as digit count grows.

Approach 2: Digit Count Matching with Powers of Two (O(d) time, O(1) space)

The key observation: if two numbers are permutations of each other, their digit frequency counts are identical. Instead of generating permutations of n, compute a digit frequency signature for n. Then iterate through all powers of two within the integer range (from 2^0 to about 2^30 for 32-bit integers). For each power, compute its digit frequency and compare it with the signature of n. If any match occurs, a valid reordering exists. This reduces the problem to counting digits using a simple array or map from the counting pattern.

The iteration over powers of two is constant (around 31 values), so the dominant cost is building digit counts of size d. The total complexity becomes O(d) time with O(1) space since the digit array has fixed size 10. Implementations often use arrays or maps from a hash table perspective to compare signatures efficiently.

This approach avoids permutation generation entirely and converts the problem into a frequency comparison task. Conceptually it blends ideas from math and digit counting to exploit the small set of candidate numbers.

Recommended for interviews: Interviewers expect the digit-count matching approach. It shows you recognized the permutation equivalence trick and avoided factorial enumeration. Explaining the backtracking version first demonstrates baseline reasoning, but the optimized frequency comparison shows stronger algorithmic insight and leads to a clean O(d) solution.