Reordered Power of 2

Problem Statement

Given an integer n, your task is to determine if it's possible to rearrange its digits to form a new number that is a power of two. In this rearrangement, the leading digit must not be zero. You need to decide and return true if it's feasible to rearrange the digits to generate a number that's a power of two, otherwise return false.

Examples

Example 1

Input:

n = 1

Output:

true

Example 2

Input:

n = 10

Output:

false

Constraints

• 1 <= n <= 109

Approach and Intuition

To tackle this problem, the central idea is to generate permutations of the digits of n and check each permutation to see if it forms a power of two. Here are the steps involved in more detail:

1. Extract Digits: Start by converting the integer n into its constituent digits.
2. Generate Permutations: Create all possible valid permutations of these digits. A valid permutation is one where the first digit is not zero.
3. Check for Power of Two: For each valid permutation, convert it back into an integer and check if this integer is a power of two. An integer is a power of two if there exists an integer x such that (2^x) equals the integer.
4. Return the Result: If any one of the permutations meets the criterion of being a power of two, return true. If none of the permutations qualify, return false.

• The key challenge here lies in efficiently generating and checking permutations, especially given that n can be as large as 10^9, which implies up to 10 digits and potentially a factorial scale permutation count in the naive approach.
• To optimize, we may also consider directly computing and storing powers of two within the permissible range and simply check if any permutation matches these precomputed values. This avoids the need to check if a number is a power of two from scratch each time.

These approaches hinge on the properties of digit rearrangement and the mathematical properties of powers of two. By exploring these efficiently, we can determine the answer to the given problem.

Solutions

class Solution {
    public boolean isPowerOfTwoReordered(int number) {
        int[] digitCount = computeDigitCount(number);
        for (int power = 0; power < 31; power++)
            if (Arrays.equals(digitCount, computeDigitCount(1 << power)))
                return true;
        return false;
    }
    
    public int[] computeDigitCount(int value) {
        int[] countArray = new int[10];
        while (value > 0) {
            countArray[value % 10]++;
            value /= 10;
        }
        return countArray;
    }
}