Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Move from brute-force thinking to an efficient approach using hash map strategy.
You are given an integer n. We reorder the digits in any order (including the original order) such that the leading digit is not zero.
Return true if and only if we can do this so that the resulting number is a power of two.
Example 1:
Input: n = 1 Output: true
Example 2:
Input: n = 10 Output: false
Constraints:
1 <= n <= 109Problem summary: You are given an integer n. We reorder the digits in any order (including the original order) such that the leading digit is not zero. Return true if and only if we can do this so that the resulting number is a power of two.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map · Math
1
10
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #869: Reordered Power of 2
class Solution {
public boolean reorderedPowerOf2(int n) {
String target = f(n);
for (int i = 1; i <= 1000000000; i <<= 1) {
if (target.equals(f(i))) {
return true;
}
}
return false;
}
private String f(int x) {
char[] cnt = new char[10];
for (; x > 0; x /= 10) {
cnt[x % 10]++;
}
return new String(cnt);
}
}
// Accepted solution for LeetCode #869: Reordered Power of 2
func reorderedPowerOf2(n int) bool {
target := f(n)
for i := 1; i <= 1000000000; i <<= 1 {
if bytes.Equal(target, f(i)) {
return true
}
}
return false
}
func f(x int) []byte {
cnt := make([]byte, 10)
for x > 0 {
cnt[x%10]++
x /= 10
}
return cnt
}
# Accepted solution for LeetCode #869: Reordered Power of 2
class Solution:
def reorderedPowerOf2(self, n: int) -> bool:
def f(x: int) -> List[int]:
cnt = [0] * 10
while x:
x, v = divmod(x, 10)
cnt[v] += 1
return cnt
target = f(n)
i = 1
while i <= 10**9:
if f(i) == target:
return True
i <<= 1
return False
// Accepted solution for LeetCode #869: Reordered Power of 2
impl Solution {
pub fn reordered_power_of2(n: i32) -> bool {
fn f(mut x: i32) -> [u8; 10] {
let mut cnt = [0u8; 10];
while x > 0 {
cnt[(x % 10) as usize] += 1;
x /= 10;
}
cnt
}
let target = f(n);
let mut i = 1i32;
while i <= 1_000_000_000 {
if target == f(i) {
return true;
}
i <<= 1;
}
false
}
}
// Accepted solution for LeetCode #869: Reordered Power of 2
function reorderedPowerOf2(n: number): boolean {
const f = (x: number) => {
const cnt = Array(10).fill(0);
while (x > 0) {
cnt[x % 10]++;
x = (x / 10) | 0;
}
return cnt.join(',');
};
const target = f(n);
for (let i = 1; i <= 1_000_000_000; i <<= 1) {
if (target === f(i)) {
return true;
}
}
return false;
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan the rest of the array looking for a match. Two nested loops give n × (n−1)/2 comparisons = O(n²). No extra space since we only use loop indices.
One pass through the input, performing O(1) hash map lookups and insertions at each step. The hash map may store up to n entries in the worst case. This is the classic space-for-time tradeoff: O(n) extra memory eliminates an inner loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.