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
Approach
Links
Examples
Solutions
/**
* 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