Skip to main content

869 - Reordered Power of 2

Difficulty: Medium | Pattern: Sorting + Math | Company tags: Google, Amazon

Problem Statement​

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 in a way such that the resulting number is a power of two.

Example 1:

Input: n = 1
Output: true  (1 = 2^0)

Example 2:

Input: n = 10
Output: false

Example 3:

Input: n = 46
Output: true  (64 = 2^6)

Approach: Sorted Digit Counter — O(log n)​

Key insight: Two numbers are anagrams of each other iff their sorted digit strings are equal. Check if n's sorted digits match any power of 2's sorted digits.

from collections import Counter

def reorderedPowerOf2(n: int) -> bool:
    count = Counter(str(n))
    
    power = 1
    while power <= 10**9:
        if Counter(str(power)) == count:
            return True
        power *= 2
    
    return False

Algorithm Flow​

Alternative: Sort Digits​

def reorderedPowerOf2(n: int) -> bool:
    s = sorted(str(n))
    return any(s == sorted(str(1 << i)) for i in range(30))

Dry Run​

n = 46: sorted digits = ['4','6']

Check powers of 2:

  • 64: sorted = ['4','6'] → match! return True ✓

n = 10: sorted digits = ['0','1']

No power of 2 up to 10^9 has sorted digits ['0','1'] → False ✓

Edge Cases​

  • Single digit n=1,2,4,8 → True (already powers of 2)
  • Leading zeros issue: Counter approach handles this since we compare digit multisets, not the number itself

Complexity​

  • Time: O(log n × digit_count) ≈ O(log² n)
  • Space: O(log n) for counter

Key Terms​

TermDefinition
Digit multiset / anagramTwo numbers are digit-anagrams if sorting (or counting) their digits produces identical results.
CounterA hashmap of digit → frequency, used to compare digit multisets in O(1) amortized per comparison.
Power of twoA number of the form 2^k; there are only ~30 such numbers below 10^9, making brute-force enumeration feasible.
Search space boundingSince n has at most 10 digits, only powers of 2 up to 10^9 (about 30 values) need to be checked.
Canonical formSorting digits into a fixed order to normalize all reorderings of the same digits into one comparable representation.

FAQ​

Q: Can this be solved without checking every power of 2? A: Not efficiently — since digit permutations don't preserve numeric value in a simple formula, the practical approach is to compare n's digit signature against the ~30 powers of 2 within its digit-length range.

Q: What if n has a leading zero after reordering? A: The problem only asks whether some reordering with a non-zero leading digit forms a power of 2; comparing digit multisets (Counter/sorted digits) directly answers this without needing to enumerate permutations, since any valid power of 2 with no leading zero will naturally match the multiset only if it's achievable.

Q: How would this change if we had to also return the actual reordered number? A: You'd need to generate a valid permutation of n's digits equal to the matching power of 2 — but since digit multisets uniquely determine the matching power's digit string, you can just output that power of 2 directly.

Q: What's the follow-up interviewers usually ask? A: "What if n could be arbitrarily large (not bounded by 10 digits)?" — this pushes toward discussing big-integer digit counting and why the power-of-2 search space stays logarithmic in n.

Q: Why is sorting or counting digits sufficient to detect an anagram relationship? A: Because reordering digits doesn't change which digits exist or how many of each — only their positions. Two numbers are digit-permutations of each other if and only if their sorted digit sequences (or digit frequency counts) are identical.

Quick Revision​

  • Reordering digits can only permute existing digits — it can never add, remove, or change a digit's value.
  • Two numbers are digit-reorderings of each other iff their sorted digit strings (or Counters) match.
  • Only ~30 powers of 2 exist below 10^9, so brute-force checking all of them is O(1)-ish in practice.
  • Compare n's digit Counter (or sorted digit list) against each power of 2's digit Counter.
  • No need to generate actual permutations — multiset comparison sidesteps combinatorial explosion.
  • Time complexity: O(log n × digit_count) ≈ O(log² n); space: O(log n) for the counter.
  • Edge case: single-digit powers of 2 (1, 2, 4, 8) trivially return True.
  • The "Alternative: Sort Digits" version is a more concise one-liner using sorted(str(x)).
  • 246 - Strobogrammatic Number — another digit-property check problem (not present in this directory).
  • 438 - Find All Anagrams in a String — shares the anagram/multiset-comparison pattern (not present in this directory).
  • 242 - Valid Anagram — same core technique of comparing character/digit frequency counts, see 242-ValidAnagram.md.