# Reordered Power of 2
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/reordered-power-of-2)
Canonical: https://scaleengineer.com/dsa/problems/reordered-power-of-2
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Counting](https://scaleengineer.com/dsa/patterns/counting), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Hash Table
---
## Problem
You are given an integer `n`. We reorder the digits in any order (including the original order) such that the leading digit is not zero.

Return `true` _if and only if we can do this so that the resulting number is a power of two_.

**Example 1:**

**Input:** n = 1
**Output:** true

**Example 2:**

**Input:** n = 10
**Output:** false

**Constraints:**

* `1 <= n <= 109`

# Approaches
## Brute-force with Permutations
This approach directly simulates the problem statement by generating every possible number that can be formed by reordering the digits of the input `n`. It then checks if any of these reordered numbers is a power of two.
**Time:** O(d! * d), where `d` is the number of digits in `n`. Generating all unique permutations of `d` digits takes O(d!) time. For each permutation, converting it to a number and checking if it's a power of two takes O(d) time. Given `n <= 10^9`, `d` can be up to 10. `10!` is 3,628,800, making this approach computationally expensive. · **Space:** O(d), where `d` is the number of digits in `n`. This space is used for the recursion stack (which can go up to `d` levels deep) and the `used` boolean array.
**Pros:** Conceptually straightforward as it directly models the problem's requirements.; Guaranteed to find a solution if one exists.
**Cons:** Extremely inefficient due to its factorial time complexity.; Likely to cause a 'Time Limit Exceeded' error on most platforms for inputs with a moderate number of unique digits (e.g., 8-10 digits).
### Explanation
The core of this method is a backtracking algorithm to generate all permutations of the digits of `n`. First, we convert `n` to a string and then to a character array. Sorting this array is a crucial step to efficiently handle duplicate digits and avoid generating the same permutation multiple times.

The recursive function explores all possibilities. In each step, it picks an unused digit, appends it to the current permutation being built, and recurses. After the recursive call returns, it backtracks by removing the digit and marking it as unused again, allowing it to be used in a different position.

Once a full-length permutation is formed, we check two conditions: the leading digit must not be zero, and the number formed must be a power of two. If both are true, we've found a solution.

```java
class Solution {
    public boolean reorderedPowerOf2(int n) {
        char[] digits = String.valueOf(n).toCharArray();
        java.util.Arrays.sort(digits); // Sort to handle duplicates efficiently
        boolean[] used = new boolean[digits.length];
        return generatePermutations(digits, new StringBuilder(), used);
    }

    private boolean generatePermutations(char[] digits, StringBuilder currentPermutation, boolean[] used) {
        if (currentPermutation.length() == digits.length) {
            // A full permutation has been formed
            // Check for leading zero
            if (currentPermutation.charAt(0) == '0') {
                return false;
            }
            long num = Long.parseLong(currentPermutation.toString());
            // Check if it's a power of two
            return (num > 0) && ((num & (num - 1)) == 0);
        }

        for (int i = 0; i < digits.length; i++) {
            if (used[i]) {
                continue;
            }
            // Skip duplicates to generate unique permutations
            if (i > 0 && digits[i] == digits[i - 1] && !used[i - 1]) {
                continue;
            }

            used[i] = true;
            currentPermutation.append(digits[i]);

            if (generatePermutations(digits, currentPermutation, used)) {
                return true; // Found a valid power of two
            }

            // Backtrack
            currentPermutation.deleteCharAt(currentPermutation.length() - 1);
            used[i] = false;
        }

        return false;
    }
}
```
### Algorithm
*   Convert the input integer `n` into a character array representing its digits.
*   To handle duplicate digits efficiently and generate unique permutations, sort the character array.
*   Use a recursive backtracking algorithm to generate all unique permutations of the digits.
*   For each generated permutation:
    *   Check if the leading digit is '0'. If it is, this permutation is invalid, so skip it.
    *   If the leading digit is not '0', convert the permutation of characters back into a number.
    *   Check if this number is a power of two. A positive integer `x` is a power of two if and only if `(x & (x - 1)) == 0`.
    *   If a power of two is found, we can immediately return `true`.
*   If the recursion completes without finding any permutation that is a power of two, return `false`.

## Precomputation with Sorted String Representation
A much more efficient approach is to realize that we don't need to generate permutations of the input `n`. Instead, we can check if the digits of `n` can form any valid power of two. Two numbers are permutations of each other if they have the exact same multiset of digits. We can check this by creating a canonical representation for the digit multiset, such as a sorted string of the digits. We precompute the sorted digit strings for all relevant powers of two and store them in a hash set for fast lookups.
**Time:** O(log n * log(log n)). Let `d = log10(n)` be the number of digits in `n`. The time complexity is dominated by processing the input `n`. Converting `n` to a string takes O(d), and sorting its `d` digits takes O(d log d). The lookup in the hash set takes O(d) on average. Thus, the overall complexity is O(d log d). · **Space:** O(1). The `HashSet` stores a constant amount of data. There are 30 powers of two to consider, and the longest number (`2^29`) has 9 digits. The total space is fixed and does not depend on the input `n`.
**Pros:** Very fast query time after the initial one-time precomputation.; The precomputation is also very fast and only needs to be done once.; Simple and clean implementation.
**Cons:** Involves string conversions and sorting, which can be slightly less performant than pure arithmetic operations.; Requires a small amount of static memory for the precomputed set.
### Explanation
The constraint `n <= 10^9` is key. This means any reordered number will also have at most 10 digits. The largest power of two less than `10^10` is `2^33`, but we only need to consider powers of two up to `10^9`, which is `2^29`. This gives us a small, finite set of only 30 target numbers (`2^0` to `2^29`).

We can pre-calculate the sorted digit string for each of these 30 powers of two and store them in a `HashSet`. This is a one-time cost.

When the `reorderedPowerOf2` function is called with an input `n`, we simply compute the sorted digit string for `n` and check if it exists in our precomputed set. This transforms the problem from a complex permutation search into a simple set lookup.

```java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    private static final Set<String> powerOfTwoSortedStrings = new HashSet<>();

    // Precompute the canonical representations of powers of two.
    static {
        for (int i = 0; i < 30; i++) {
            int powerOfTwo = 1 << i;
            char[] chars = String.valueOf(powerOfTwo).toCharArray();
            Arrays.sort(chars);
            powerOfTwoSortedStrings.add(new String(chars));
        }
    }

    public boolean reorderedPowerOf2(int n) {
        char[] nChars = String.valueOf(n).toCharArray();
        Arrays.sort(nChars);
        String sortedNString = new String(nChars);
        
        return powerOfTwoSortedStrings.contains(sortedNString);
    }
}
```
### Algorithm
*   Recognize that two numbers are reorderings of each other if and only if their sorted digit strings are identical. This sorted string can serve as a canonical representation.
*   Precompute the canonical representations for all powers of two that are within the problem's constraints. Since `n <= 10^9`, we only need to consider powers of two up to `2^29`.
*   Create a `HashSet` to store these precomputed canonical strings for O(1) average time lookups.
*   In a one-time setup (e.g., a static block), iterate from `i = 0` to `29`:
    *   Calculate `p = 1 << i`.
    *   Convert `p` to a string, sort its characters, and add the resulting string to the `HashSet`.
*   For any given input `n`:
    *   Convert `n` to its own canonical representation by sorting its digits.
    *   Check if this new string exists in the precomputed `HashSet`.
    *   Return the result of the check.

## Digit Counting Comparison
This is the most optimal approach. It improves upon the previous idea by using a more efficient canonical representation: a frequency count of digits. Instead of converting numbers to strings and sorting them, we count the occurrences of each digit (0 through 9). Two numbers are permutations of each other if and only if their digit counts are identical. We can compare the digit count of the input `n` with the digit counts of the first 30 powers of two.
**Time:** O(log n). Let `d = log10(n)` be the number of digits in `n`. The time is dominated by the initial call to `countDigits(n)`, which takes O(d) time. The subsequent loop runs a constant 30 times. Inside the loop, `countDigits` is called on powers of two, which have at most 10 digits, making it an O(1) operation. Array comparison also takes O(1) time (for a fixed size of 10). Therefore, the total time complexity is O(log n). · **Space:** O(1). The space required is for two integer arrays of size 10 to store the digit counts. This is constant and does not depend on the size of the input `n`.
**Pros:** Extremely efficient, as it avoids costly permutations and string operations.; The main logic runs in a small, constant number of iterations.; Minimal space usage.
**Cons:** The logic might be slightly less intuitive at first glance compared to direct permutation.
### Explanation
This method avoids string manipulation entirely, relying on faster integer arithmetic. We define a helper function that takes an integer and returns an array of size 10, where each index `i` stores the count of digit `i` in the number.

First, we compute this digit-count array for the input `n`. Then, we loop through powers of two, from `2^0` up to `2^29`. In each iteration, we compute the digit-count array for the current power of two and compare it with the one from `n`. The `java.util.Arrays.equals()` method provides a convenient way to compare the two arrays. If a match is found, we return `true` immediately. If we exhaust all 30 powers of two without a match, we can be certain that no such reordering is possible and return `false`.

```java
import java.util.Arrays;

class Solution {
    public boolean reorderedPowerOf2(int n) {
        int[] nCounts = countDigits(n);

        // Iterate through powers of 2
        for (int i = 0; i < 30; i++) {
            int powerOfTwo = 1 << i;
            int[] pCounts = countDigits(powerOfTwo);
            
            // If the digit counts are the same, it's a valid reordering
            if (Arrays.equals(nCounts, pCounts)) {
                return true;
            }
        }
        
        return false;
    }

    // Helper function to count digit frequencies of a number
    private int[] countDigits(int num) {
        int[] counts = new int[10];
        while (num > 0) {
            counts[num % 10]++;
            num /= 10;
        }
        return counts;
    }
}
```
### Algorithm
*   The fundamental insight is that two numbers are reorderings of each other if and only if they have the same frequency count for each digit (0-9).
*   Create a helper function, `countDigits(int num)`, that returns a frequency array (e.g., `int[10]`) of the digits in `num`.
*   In the main function, first call `countDigits(n)` to get the digit frequency map of the input number.
*   Iterate through the powers of two that are relevant. Since `n <= 10^9`, we only need to check powers of two from `2^0` to `2^29` (a total of 30 numbers).
*   In each iteration of the loop (for `i` from 0 to 29):
    *   Calculate the power of two, `p = 1 << i`.
    *   Call `countDigits(p)` to get its digit frequency map.
    *   Compare the frequency map of `p` with the frequency map of `n`.
    *   If the two frequency maps are identical, it means `n` can be reordered to form this power of two. Return `true`.
*   If the loop finishes without finding any matching frequency map, it's impossible to form a power of two. Return `false`.

# Solutions
### Java

```java
class Solution {
public
  boolean reorderedPowerOf2(int n) {
    String s = convert(n);
    for (int i = 1; i <= Math.pow(10, 9); i <<= 1) {
      if (s.equals(convert(i))) {
        return true;
      }
    }
    return false;
  }
private
  String convert(int n) {
    char[] cnt = new char[10];
    for (; n > 0; n /= 10) {
      cnt[n % 10]++;
    }
    return new String(cnt);
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool reorderedPowerOf2(int n) {
    vector<int> s = convert(n);
    for (int i = 1; i <= pow(10, 9); i <<= 1)
      if (s == convert(i))
        return true;
    return false;
  }
  vector<int> convert(int n) {
    vector<int> cnt(10);
    for (; n; n /= 10)
      ++cnt[n % 10];
    return cnt;
  }
};

```

### Python

```python
class Solution:
    def reorderedPowerOf2(self, n: int) -> bool: def convert(n): cnt = [0] * 10 while n: n, v = divmod(n, 10) cnt[v] += 1 return cnt i, s = 1, convert(n) while i <= 10 ** 9: if convert(i) == s: return True i <<= 1 return False

```