#869 Reordered Power of 2 - Solution

In #869 Reordered Power of 2, the goal is to determine whether the digits of an integer n can be rearranged to form a power of two. A key observation is that if two numbers contain the same digits, they will have the same digit frequency or the same sorted digit sequence.

A common approach is to enumerate all powers of two within the integer range and compare their digit patterns with that of n. For each candidate power of two, either sort its digits or build a digit frequency count. If the pattern matches the one computed for n, then a valid reordering exists.

Using a counting-based signature (e.g., frequency of digits 0–9) is typically faster than sorting for repeated checks. Since there are only about 30 powers of two within the 32-bit integer range, the enumeration remains efficient. This makes the solution practical with near-constant time complexity and small auxiliary space.

Approach	Time Complexity	Space Complexity
Enumerate powers of 2 with sorted digit comparison	O(k log k * log N)	O(k)
Digit frequency counting (hash/count signature)	O(k * log N)	O(1)

Solutions (12)

Digit Count Matching with Powers of Two

One approach to solve the problem is to leverage the fact that two numbers with the same digits in different orders will have the same digit frequency (or count of each digit). For the given number n, we aim to check if its digits can be rearranged to form any power of two. To achieve this:

Precompute all powers of two up to 10^9 and store their digit frequency in a set.
For the input number n, calculate its digit frequency and check if it exists in the set.

Time Complexity: O(1) because the number of power of twos checked (31) and the frequency array size (10) are constant.
Space Complexity: O(1) as only small fixed-size integer arrays are used.

C C++Java Python C#JavaScript

1using System;
2using System.Linq;
3
4public class Solution {
5    public bool ReorderedPowerOf2(int n) {
6        var inputDigits = n.ToString().OrderBy(c => c).ToArray();
7        for (int i = 0; i < 31; i++) {
8            var powerDigits = (1 << i).ToString().OrderBy(c => c).ToArray();
9            if (inputDigits.SequenceEqual(powerDigits)) {
10                return true;
11            }
12        }
        return false;
    }

    public static void Main(string[] args) {
        Solution solution = new Solution();
        Console.WriteLine(solution.ReorderedPowerOf2(1));  // Output: True
    }
}

Explanation

C# follows the concept of sorted digit sequences much like other language implementations. It compares the reordered digits of n to those of each power of two, confirming if a reordered form equals any such power.

Backtracking Approach

A backtracking method can be employed by generating permutations of the digits of the number n and checking if any results in a power of two. Given the constraint, this method needs optimization to efficiently discard invalid permutations early.

Generate all valid permutations of n's digits where the leading digit isn't zero.
Track numbers that form powers of two during permutations.

Not provided due to complexity constraints in inline format.

C C++Java Python C#JavaScript

1using namespace std;

bool canFormPowerOf2(string perm) {
    if (perm[0] == '0') return false;
    int num = stoi(perm);
    return (num & (num - 1)) == 0;
}

bool backtracking(string& nStr, string perm, vector<bool>& used) {
    if (perm.size() == nStr.size()) {
        return canFormPowerOf2(perm);
    }
    for (int i = 0; i < nStr.size(); ++i) {
        if (used[i] || (i > 0 && nStr[i] == nStr[i-1] && !used[i-1])) continue;
        used[i] = true;
        if (backtracking(nStr, perm + nStr[i], used)) return true;
        used[i] = false;
    }
    return false;
}

bool reorderedPowerOf2(int n) {
    string nStr = to_string(n);
    vector<bool> used(nStr.size(), false);
    sort(nStr.begin(), nStr.end());
    return backtracking(nStr, "", used);
}

int main() {
    int n = 10;
    cout << std::boolalpha << reorderedPowerOf2(n) << endl;
    return 0;
}