869. Reordered Power of 2

二刷 08/2022

Version #1 Count digits of power of 2s less than Integer.MAX_VALUE(2^32 - 1)

Time O(logN + 32log(2^32)*10) ~ O(logN)

Space O(1)

Runtime: 1 ms, faster than 100.00% of Java online submissions for Reordered Power of 2.

Memory Usage: 41.2 MB, less than 54.00% of Java online submissions for Reordered Power of 2.

class Solution {

    public boolean reorderedPowerOf2(int n) {

        int[] digits = countDigits(n);

        for (int i = 0; i < 32; i++) {

            if (Arrays.equals(digits, countDigits(1 << i))) {

                return true;

            }

        }

        return false;

    }

    

    private int[] countDigits(int x) {

        int[] digits = new int[10];

        while (x > 0) {

            digits[x % 10]++;

            x /= 10;

        }

        return digits;

    }

}

一刷
Version #1 Check  the count of digits and compare with all power of 2s
My original idea is to generate all permutations and check, however it seems not efficient

84.75 %
class Solution {
    public boolean reorderedPowerOf2(int N) {
int[] curr = count(N);
for (int i = 0; i < 32; i++) {
if (Arrays.equals(count(1 << i), curr)) {
return true;
}
}
return false;
}
private int[] count(int x) {
int[] counter = new int[10];
while(x > 0) {
counter[x % 10]++;
x /= 10;
}
return counter;
}
}