Reordered Power of 2

medium math counting sorting

Problem

Given a positive integer n, return true if some permutation of its digits (with no leading zero) equals a power of two. Two numbers use the same digits exactly when their sorted digit strings — or digit-count signatures — match, so we just compare n against each power of two.

Inputn = 46

Outputtrue

Rearranging 46 gives 64 = 2⁶.

def reordered_power_of_2(n):
    sig = sorted(str(n))
    p = 1
    while p <= 10 ** 9:
        if sorted(str(p)) == sig:
            return True
        p *= 2
    return False

function reorderedPowerOf2(n) {
  const sig = (x) => String(x).split("").sort().join("");
  const target = sig(n);
  for (let p = 1; p <= 1e9; p *= 2) {
    if (sig(p) === target) return true;
  }
  return false;
}

boolean reorderedPowerOf2(int n) {
    String target = sig(n);
    for (long p = 1; p <= 1_000_000_000L; p *= 2) {
        if (sig((int) p).equals(target)) return true;
    }
    return false;
}
private String sig(int x) {
    char[] c = Integer.toString(x).toCharArray();
    Arrays.sort(c);
    return new String(c);
}

string sig(long long x) {
    string s = to_string(x);
    sort(s.begin(), s.end());
    return s;
}
bool reorderedPowerOf2(int n) {
    string target = sig(n);
    for (long long p = 1; p <= 1000000000LL; p *= 2)
        if (sig(p) == target) return true;
    return false;
}

Explanation

Two numbers are rearrangements of each other exactly when they use the same digits — same count of each digit. So instead of generating every permutation of n, we just compare it against every power of two.

We turn each number into a signature by sorting its digits as a string. For example 46 and 64 both sort to "46", so they share a signature. If n's signature matches some power of two's signature, the answer is true.

The loop walks the powers 1, 2, 4, 8, ... up to about a billion (the input limit), comparing sorted(str(p)) to sig. There are only around 30 such powers, so this is very fast.

Example: n = 46 gives sig = "46". When the loop reaches p = 64, its sorted digits are also "46" — a match, so we return true.

It works because checking the digit signature is the same as asking "can these digits be reordered into that number," and we only ever need to test the handful of powers of two.

Time: O(log²(max)) Space: O(log(max))