869: Reordered Power of 2

Difficulty: Medium

Topics: Hash Table, Math, Sorting, Counting, Enumeration

Companies: Google, Amazon, Microsoft

Pro Tip: The key insight is that there are only 30 possible powers of 2 within the integer range. Compare digit frequencies instead of generating all permutations.

Problem Statement

Given an integer n, return true if and only if you can rearrange its digits to form a power of two (without leading zeros).

Example 1

Input: n = 1

Output: true

Explanation: 1 is already a power of 2 (2⁰)

Example 2

Input: n = 10

Output: false

Explanation: Rearrangements are "10" or "01". "01" has a leading zero and is invalid.

Example 3

Input: n = 46

Output: true

Explanation: Rearrange to 64 → 64 is 2⁶ (a power of two)

Problem Link: View on LeetCode ↗

Key Insight

The solution relies on these crucial observations:

There are only 30 powers of 2 within the integer range (0 to 10⁹)
Two numbers with the same digit frequencies can be rearranged to form each other
Instead of generating all permutations (O(n!)), compare digit frequencies
Leading zeros are not allowed in the rearranged number

Important: The constraint 1 ≤ n ≤ 10⁹ means we have at most 10 digits, making digit frequency comparison efficient.

Approach 1: Precomputation with Sorted Strings

Precompute all powers of 2 and store their sorted digit strings for comparison.

Algorithm Steps

Precompute all powers of 2 from 2⁰ to 2²⁹
Convert each power to a string and sort its characters
Store these sorted strings in a set
Convert input n to sorted string
Check if the sorted string exists in the set

Complexity Analysis

Time Complexity	Space Complexity
O(1)	O(1)

Constant time since 30 powers × 10 digits = fixed computation

Sorted String Precomputation

class Solution {
public:
    bool reorderedPowerOf2(int n) {
        // Precompute all powers of 2 from 2^0 to 2^29
        set<string> powerSet;
        for (int i = 0; i <= 29; i++) {
            long num = 1L << i;
            string s = to_string(num);
            sort(s.begin(), s.end());
            powerSet.insert(s);
        }
        
        // Process input n
        string t = to_string(n);
        sort(t.begin(), t.end());
        return powerSet.find(t) != powerSet.end();
    }
};

import java.util.*;

class Solution {
    public boolean reorderedPowerOf2(int n) {
        // Precompute all powers of 2 from 2^0 to 2^29
        Set<String> powerSet = new HashSet<>();
        for (int i = 0; i <= 29; i++) {
            long num = 1L << i;
            char[] chars = String.valueOf(num).toCharArray();
            Arrays.sort(chars);
            powerSet.add(new String(chars));
        }
        
        // Process input n
        char[] arr = String.valueOf(n).toCharArray();
        Arrays.sort(arr);
        return powerSet.contains(new String(arr));
    }
}

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        # Precompute all powers of 2 from 2^0 to 2^29
        power_set = set()
        for i in range(30):
            num = 1 << i
            s = sorted(str(num))
            power_set.add(tuple(s))
        
        # Process input n
        t = tuple(sorted(str(n)))
        return t in power_set

Efficiency: This approach runs in constant time since it processes a fixed number (30) of powers of 2.

Approach 2: Digit Frequency Counting

Compare the digit frequency of the input with all possible powers of 2.

Algorithm Steps

Create a frequency array for digits in input n
For each power of 2 from 2⁰ to 2²⁹:
- Create a frequency array for its digits
- Compare with input's frequency array
- Return true if they match
Return false if no match found

Complexity Analysis

Time Complexity	Space Complexity
O(1)	O(1)

Constant time since we compare at most 30 values with fixed digit counts (max 10 digits)

Digit Frequency Comparison

class Solution {
public:
    bool reorderedPowerOf2(int n) {
        // Get digit frequency of input n
        vector<int> freqN(10, 0);
        string s = to_string(n);
        for (char c : s) {
            freqN[c - '0']++;
        }
        
        // Compare with all powers of 2
        for (int i = 0; i <= 29; i++) {
            long power = 1L << i;
            string t = to_string(power);
            if (t.size() != s.size()) continue;
            
            vector<int> freqPower(10, 0);
            for (char c : t) {
                freqPower[c - '0']++;
            }
            
            if (freqN == freqPower) return true;
        }
        
        return false;
    }
};

class Solution {
    public boolean reorderedPowerOf2(int n) {
        // Get digit frequency of input n
        int[] freqN = new int[10];
        String s = String.valueOf(n);
        for (char c : s.toCharArray()) {
            freqN[c - '0']++;
        }
        
        // Compare with all powers of 2
        for (int i = 0; i <= 29; i++) {
            long power = 1L << i;
            String t = String.valueOf(power);
            if (t.length() != s.length()) continue;
            
            int[] freqPower = new int[10];
            for (char c : t.toCharArray()) {
                freqPower[c - '0']++;
            }
            
            if (Arrays.equals(freqN, freqPower)) return true;
        }
        
        return false;
    }
}

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        # Get digit frequency of input n
        s = str(n)
        freq_n = [0] * 10
        for char in s:
            freq_n[int(char)] += 1
        
        # Compare with all powers of 2
        for i in range(30):
            power = 1 << i
            t = str(power)
            if len(t) != len(s):
                continue
                
            freq_power = [0] * 10
            for char in t:
                freq_power[int(char)] += 1
                
            if freq_n == freq_power:
                return True
                
        return False

Advantage: More efficient than string sorting for large numbers since comparing arrays is O(10) = constant time.

Approach 3: Digit Frequency Hashing

Create a unique hash for digit frequencies and compare with power-of-two hashes.

Algorithm Steps

Create a unique value representing the digit frequency of input n
For each digit, add 10^digit to a running sum
Repeat for all powers of 2 from 2⁰ to 2²⁹
Return true if any power has the same hash value

Complexity Analysis

Time Complexity	Space Complexity
O(1)	O(1)

Frequency Hashing

class Solution {
public:
    bool reorderedPowerOf2(int n) {
        // Create frequency hash for input n
        long hashN = 0;
        while (n) {
            hashN += pow(10, n % 10);
            n /= 10;
        }
        
        // Compare with all powers of 2
        for (int i = 0; i <= 29; i++) {
            long num = 1L << i;
            long hashPower = 0;
            while (num) {
                hashPower += pow(10, num % 10);
                num /= 10;
            }
            if (hashN == hashPower) return true;
        }
        return false;
    }
};

class Solution {
    public boolean reorderedPowerOf2(int n) {
        // Create frequency hash for input n
        long hashN = 0;
        int temp = n;
        while (temp != 0) {
            int digit = temp % 10;
            hashN += Math.pow(10, digit);
            temp /= 10;
        }
        
        // Compare with all powers of 2
        for (int i = 0; i <= 29; i++) {
            long num = 1L << i;
            long hashPower = 0;
            long tempNum = num;
            while (tempNum != 0) {
                int digit = (int)(tempNum % 10);
                hashPower += Math.pow(10, digit);
                tempNum /= 10;
            }
            if (hashN == hashPower) return true;
        }
        return false;
    }
}

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        # Create frequency hash for input n
        hash_n = 0
        temp = n
        while temp:
            digit = temp % 10
            hash_n += 10 ** digit
            temp //= 10
        
        # Compare with all powers of 2
        for i in range(30):
            num = 1 << i
            hash_power = 0
            temp_num = num
            while temp_num:
                digit = temp_num % 10
                hash_power += 10 ** digit
                temp_num //= 10
                
            if hash_n == hash_power:
                return True
                
        return False

Optimization: This method avoids storing entire frequency arrays and uses a single numeric value for comparison.

Edge Cases and Testing

1. Single Digit Numbers

Input: 1 → Output: true (2⁰ = 1)
Input: 8 → Output: true (2³ = 8)
Input: 3 → Output: false

2. Numbers with Leading Zero Potential

Input: 10 → Output: false (only permutations: 10 and 01, both invalid)
Input: 102 → Output: false (201 and 021 have leading zeros)

3. Valid Rearrangements

Input: 46 → Output: true (64 = 2⁶)
Input: 61 → Output: true (16 = 2⁴)
Input: 812 → Output: true (128 = 2⁷)

4. Large Numbers

Input: 2147483647 → Output: false
Input: 1048576 → Output: true (2²⁰ = 1048576)

Important: Always verify that the solution correctly handles numbers that would have leading zeros when rearranged.

Detailed Explanation

The problem requires checking if a number can be rearranged (permuted) to form a power of two. The key insight is recognizing that:

128

256

512

Since there are only 30 powers of 2 in the integer range (2⁰ to 2²⁹), we can efficiently check against all of them. Instead of generating all permutations of the input number (which would be O(n!) and infeasible), we compare digit frequencies.

The solution approaches work as follows:

Precomputation: Store sorted strings or digit counts of all powers of 2
Comparison: For the input number, compute its sorted string or digit frequency
Matching: Check if any power of 2 has the same digit representation

This approach efficiently solves the problem in constant time and space since the number of powers of 2 is fixed (30) and the digit count is limited (max 10 digits).

Why it works: Two numbers can be rearranged to form each other if and only if they have identical digit frequencies.

FAQs

1. Why are there only 30 powers of 2 to consider?

Since n ≤ 10⁹, the largest power of 2 we need to consider is 2²⁹ = 536,870,912 (which is under 10⁹). 2³⁰ = 1,073,741,824 is still ≤ 10⁹, but 2³⁰ has 10 digits while 2²⁹ has 9 digits. We consider powers from 2⁰ to 2³⁰ (31 total).

2. How does the solution avoid numbers with leading zeros?

The digit frequency comparison naturally avoids leading zeros because we're comparing the actual digits present in the number. If a permutation would have a leading zero, it would require a '0' in the most significant position, but our comparison doesn't consider position, only digit presence.

3. What is the time complexity of generating all permutations?

Generating all permutations of a number with d digits would be O(d!), which is O(10!) = 3,628,800 for 10-digit numbers. This is acceptable for small d but inefficient compared to our O(1) solution.

4. Can this approach be extended to powers of other numbers?

Yes, the same digit frequency comparison technique can be used to check if a number can be rearranged to form a power of any given base. You would generate powers of that base within the number range and compare digit frequencies.

5. What is the advantage of the hashing approach?

The hashing approach (Approach 3) converts the digit frequency into a single numeric value. This allows for O(1) comparisons using primitive values instead of comparing arrays or strings.

6. How many digit combinations are possible for a d-digit number?

There are 10^d possible digit combinations, but many are invalid (like those with leading zeros). Our solution efficiently checks only the valid possibilities that are powers of two.

7. What is the largest power of 2 we need to consider?

For n ≤ 10⁹, the largest power of 2 is 2²⁹ = 536,870,912 (9 digits) and 2³⁰ = 1,073,741,824 (10 digits). We need to consider powers from 2⁰ to 2³⁰ inclusive.

8. Can negative numbers be handled?

The problem states that n is positive (1 ≤ n ≤ 10⁹), so we don't need to handle negative numbers. Powers of 2 are always positive.

9. Is the digit frequency method accurate for numbers with repeated digits?

Yes, the digit frequency method accurately captures repeated digits. For example, 338 would have two 3's and one 8, and would match a power of 2 with the same digit counts.

10. What is the space complexity of storing digit frequencies?

The space complexity is O(1) since we only store an array of 10 integers (for digits 0-9) or a single numeric hash value, regardless of input size.