Leetcode 869 - Reordered Power of 2

Link to problem

Description

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.

Solution

Today’s (2025-08-10) daily problem.

Not quite a medium level problem.

We could bin both the input and all the power of 2 numbers that fits in int32_t (input constrain is $1 \leq n \leq 10^9$, so we could actually do $2^{29}$, which is 536870912). Then, we try to see if there is a match.

Time complexity wise, creating all the bins shouldn’t be a problem as it cost constant time.

Implementation

(Implementation here actually create all bins that fits in int32_t)

class Solution {
public:
    bool reorderedPowerOf2(int n) {
        vector<vector<int>> bins(31, vector<int>(10));
        vector<int> bin(10);

        for (size_t i = 0; i < 31; i++) {
            int m = 1 << i;
            while (m) {
                bins[i][m % 10]++;
                m /= 10;
            }
        }

        while (n) {
            bin[n % 10]++;
            n /= 10;
        }

        for (size_t i = 0; i < 31; i++) {
            bool isPow = true;
            for (size_t j = 0; j < 10; j++) {
                if (bins[i][j] != bin[j]) 
                    isPow = false;
            }
            if (isPow)
                return true;
        }

        return false;
    }
};

If we feel bored enough, we could do a quick optimization. The updated one creates a chuck of continuous memory instead of vector<vector<int>>. Therefore, we could get a performance uplift from cache locality.

class Solution {
public:
    bool reorderedPowerOf2(int n) {
        vector<int> bins(310);
        vector<int> bin(10);

        for (size_t i = 0; i < 31; i++) {
            int m = 1 << i;
            while (m) {
                bins[i * 10 + m % 10]++;
                m /= 10;
            }
        }

        while (n) {
            bin[n % 10]++;
            n /= 10;
        }

        for (size_t i = 0; i < 31; i++) {
            bool isPow = true;
            for (size_t j = 0; j < 10; j++) {
                if (bins[i * 10 + j] != bin[j]) 
                    isPow = false;
            }
            if (isPow)
                return true;
        }

        return false;
    }
};

(Note that I’m bored enough to optimize this. But I’m not really that bored to try and get some accurate execution time and choose to believe the time Leetcode gave me.)