869. Reordered Power of 2

Description

Starting with a positive 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 2.

Constraints

1. 1 <= N <= 10^9

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: 1

Output: true

Example 2

Input: 10

Output: false

Example 3

Input: 16

Output: true

Example 4

Input: 24

Output: false

Example 5

Input: 46

Output: true

Solutions

Solution 1

/**
 * Time complexity : O(log^2N). There are logN different candidate powers of 2, 
 *    and each comparison has O(logN) time complexity.
 * Space complexity : O(logN).
 */

class Solution {
    public boolean reorderedPowerOf2(int N) {
        int[] inputDigitFreqCount = getFreqCount(N);
        for(int i = 0; i < 31; i++) {
            int powerOf2 = 1 << i;
            int[] powerOf2FreqCount = getFreqCount(powerOf2);
            if(Arrays.equals(inputDigitFreqCount, powerOf2FreqCount)) {
                return true;
            }
        }
        return false;
    }
    
    private int[] getFreqCount(int n) {
        int[] digitFreq = new int[10];
        while(n > 0) {
            digitFreq[n%10]++;
            n /= 10;
        }
        return digitFreq;
    }
}

Follow up