Reordered Power of 2

869. Reordered Power of 2

class Solution {
    class Dec {
        int cnt[10] {0};
        int len = 0;
        public:
        Dec(int n) {
            while (n) {
                ++cnt[n % 10];
                n /= 10;
                ++len;
            }
        }

        bool isSameCnt(const Dec &other) {
            for (int i = 0;i < 10; ++i) {
                if (this->cnt[i] != other.cnt[i]) {
                    return false;
                }
            }
            return true;
        }

        int length() {
            return len;
        }

    };

public:
    bool reorderedPowerOf2(int n) {
        Dec d(n);

        int po2 = 1;
        while (Dec(po2).length() < d.length()) {
            po2 <<= 1;
        }

        while (0 < po2) {
            Dec p(po2);
            if (d.length() != p.length()) {
                break;
            }
            if (d.isSameCnt(p)) {
                return true;
            }
            po2 <<= 1;
        }
        return false;
    }
};

각 자리수의 개수만 같으면 재배열 해서 같은 값을 만들 수 있으므로, 각 자리수의 숫자 개수가 2의 거듭제곱의 각 자리수의 숫자 개수와 같은 것이 있다면 true, 없다면 false.

처음에는 n의 각 자리 숫자 수열의 순,열이 2의 거듭제곱을 이룰 수 있는지 확인해햐할것 같았는데, 이러면 O(n!) 이 되어서 숫자 개수 비교하는게 훨씬 빠르게 답을 낼 수 있다.

Time: O(lon(n))
int 에서 각 숫자의 개수를 세는데에 log(n)
2의 거듭제곱에 대한 루프를 포함하면 O(log(n) * log(p))

Space: O(1)
n 크기와 상관없이 카운트 세는데 필요한 공간은 10개가 필요하다.