Reordered Power of 2 — Solution in Python, Java & C++
Reordered Power of 2 solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Reordered Power of 2 is a medium coding problem on math, counting and enumeration, asked in Amazon, Google and Adobe interviews.
- Difficulty: Medium
- Topics: Math, Counting, Enumeration
- Asked at: Amazon, Google, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You may reorder the digits of n in any way, as long as the result has no leading zero.
Return true if some reordering is a power of two.
Example 1
Input: n = 16
Output: true
Explanation: 16 is already 2⁴.
Example 2
Input: n = 46
Output: true
Explanation: Reordering to 64 gives 2⁶.
Example 3
Input: n = 10
Output: false
Explanation: The only reorderings are 10 and 01, and neither is a power of two.
Constraints
1 <= n <= 1000000000
Hints for Reordered Power of 2
Hint 1
Enumerating every permutation is wasteful — there are only about 30 powers of two in range.
Hint 2
Two numbers are reorderings of each other exactly when they have the same digit multiset.
Hint 3
So compare a digit-count signature of
nagainst the signature of each power of two.
How to solve Reordered Power of 2
Flip the search around. Instead of generating permutations of n, generate the handful of powers of two in range and test whether any shares n's digit multiset.
Approach
- Write a helper that turns a number into a 10-slot digit-count signature.
- Compute the signature of
n. - Walk
p = 1, 2, 4, …whilepstays within the input bound, comparing signatures. - Return
trueon the first match.
Why it works
Two numbers are permutations of one another precisely when their digit counts agree — and the leading-zero rule is automatic, because a power of two never starts with 0 and the signature comparison already forces equal digit counts.
Complexity
- Time —
O(30 · log n) - Space —
O(1)
Pitfalls
- Generating all permutations is up to 10! and needlessly slow.
- Sorting the digit strings also works, but the counts version avoids a string sort per candidate.
- The loop bound must cover
2^30, which exceeds the input ceiling — stop once the power passes it.
Reference solution
Python
def reorderedPowerOf2(n: int) -> bool:
def sig(v: int):
count = [0] * 10
while v > 0:
count[v % 10] += 1
v //= 10
return tuple(count)
want = sig(n)
p = 1
while p <= 1000000000:
if sig(p) == want:
return True
p *= 2
return FalseJava
public static boolean reorderedPowerOf2(int n) {
String want = digitSig(n);
for (long p = 1; p <= 1000000000L; p *= 2) {
if (digitSig((int) p).equals(want)) return true;
}
return false;
}
static String digitSig(int v) {
int[] count = new int[10];
while (v > 0) {
count[v % 10]++;
v /= 10;
}
return Arrays.toString(count);
}C++
static string digitSig(int v) {
vector<int> count(10, 0);
while (v > 0) {
count[v % 10]++;
v /= 10;
}
string s;
for (int c : count) s += to_string(c) + ",";
return s;
}
bool reorderedPowerOf2(int n) {
string want = digitSig(n);
for (long long p = 1; p <= 1000000000LL; p *= 2) {
if (digitSig((int) p) == want) return true;
}
return false;
}JavaScript
var reorderedPowerOf2 = function(n) {
var sig = function(v) {
var count = [];
for (var t = 0; t < 10; t++) count.push(0);
while (v > 0) {
count[v % 10]++;
v = Math.floor(v / 10);
}
return count.join(",");
};
var want = sig(n);
for (var p = 1; p <= 1000000000; p *= 2) {
if (sig(p) === want) return true;
}
return false;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.