869. Reordered Power of 2

Time: O(log n)

Space: O(log n)

Intuition

Check if any permutation of digits of n forms a power of 2. Compare sorted-digit form of n with sorted-digit forms of all powers of 2 up to 10^9.

Algorithm

1Compute digit frequency of n.
2For each power of 2 (1,2,4,...,2^29): compare digit frequencies.
3Return true if any match.

Common Pitfalls

•Compare digit counts not values. Leading zeros are invalid but not a concern since powers of 2 never start with 0.

869.cs

// Approach: Encode digit frequencies as a single integer; compare n's encoding against the encodings of all 30 powers of 2.
// Time: O(log n) Space: O(log n)

public class Solution
{
    public bool ReorderedPowerOf2(int n)
    {
        int count = Counter(n);

        for (int i = 0; i < 30; ++i)
        {
            if (Counter(1 << i) == count)
                return true;
        }

        return false;
    }

    private int Counter(int n)
    {
        int count = 0;

        while (n > 0)
        {
            count += (int)Math.Pow(10, n % 10);
            n /= 10;
        }

        return count;
    }
}

Was this solution helpful?