Reordered Power of 2

• 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.

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.

1class Solution {2    public boolean reorderedPowerOf2(int n) {3        char[] digits = String.valueOf(n).toCharArray();4        java.util.Arrays.sort(digits); // Sort to handle duplicates efficiently5        boolean[] used = new boolean[digits.length];6        return generatePermutations(digits, new StringBuilder(), used);7    }8 9    private boolean generatePermutations(char[] digits, StringBuilder currentPermutation, boolean[] used) {10        if (currentPermutation.length() == digits.length) {11            // A full permutation has been formed12            // Check for leading zero13            if (currentPermutation.charAt(0) == '0') {14                return false;15            }16            long num = Long.parseLong(currentPermutation.toString());17            // Check if it's a power of two18            return (num > 0) && ((num & (num - 1)) == 0);19        }20 21        for (int i = 0; i < digits.length; i++) {22            if (used[i]) {23                continue;24            }25            // Skip duplicates to generate unique permutations26            if (i > 0 && digits[i] == digits[i - 1] && !used[i - 1]) {27                continue;28            }29 30            used[i] = true;31            currentPermutation.append(digits[i]);32 33            if (generatePermutations(digits, currentPermutation, used)) {34                return true; // Found a valid power of two35            }36 37            // Backtrack38            currentPermutation.deleteCharAt(currentPermutation.length() - 1);39            used[i] = false;40        }41 42        return false;43    }44}

• 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.

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.

1import java.util.Arrays;2import java.util.HashSet;3import java.util.Set;4 5class Solution {6    private static final Set<String> powerOfTwoSortedStrings = new HashSet<>();7 8    // Precompute the canonical representations of powers of two.9    static {10        for (int i = 0; i < 30; i++) {11            int powerOfTwo = 1 << i;12            char[] chars = String.valueOf(powerOfTwo).toCharArray();13            Arrays.sort(chars);14            powerOfTwoSortedStrings.add(new String(chars));15        }16    }17 18    public boolean reorderedPowerOf2(int n) {19        char[] nChars = String.valueOf(n).toCharArray();20        Arrays.sort(nChars);21        String sortedNString = new String(nChars);22        23        return powerOfTwoSortedStrings.contains(sortedNString);24    }25}

• 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.

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.

1import java.util.Arrays;2 3class Solution {4    public boolean reorderedPowerOf2(int n) {5        int[] nCounts = countDigits(n);6 7        // Iterate through powers of 28        for (int i = 0; i < 30; i++) {9            int powerOfTwo = 1 << i;10            int[] pCounts = countDigits(powerOfTwo);11            12            // If the digit counts are the same, it's a valid reordering13            if (Arrays.equals(nCounts, pCounts)) {14                return true;15            }16        }17        18        return false;19    }20 21    // Helper function to count digit frequencies of a number22    private int[] countDigits(int num) {23        int[] counts = new int[10];24        while (num > 0) {25            counts[num % 10]++;26            num /= 10;27        }28        return counts;29    }30}