Shivam Sharma

Posted on

# Leetcode 869. Reordered Power of 2 [Solution]

The question is a little bit tricky but once you get the trick, you can easily write the code.

Difficulty: Medium

## Problem Statement

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.

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

Note:

1. `1 <= N <= 10^9`

## Explanation

So the problem is simple, we are given a number `N` and we need to check whether we can create a number from this number by changing the place of digits. Considering zero can not be at the leading position.

eg. from `2014` we can create `1024` but not `0124` and `1024 = 2^10` so answer should be `true` for this `N=2014`. For `N=12` we have two combinations `12` and `21` and both are not in any power of `2` so for `N=12` answer is `false`.

## Solution

As a naive approach, we can try to check if the number is the power of `2` for every permutation of the digits in `N` and it will result in time complexity = `O((logN)!∗logN)` but look at the constraints condition `1 <= N <= 10^9` and for various power of `2` we can see that `2^29 = 536870912` and `2^30 = 1073741824`. So instead of checking whether the permutation of `N` is a power of 2, we can check that any of the numbers among `2^x ; x=0,1,2...29` has the same number of digits and same frequency of digits with `N`. If yes then this `2^x` can be created from `N`.

eg. If `N=23` then,

1. We'll check if `2^0 = 1` can be created using `23` by checking the number of digits in `2^0 = 1` and `23` as the number of digits are not equal in `1` and `23` so `1` can not be created from `23`.
2. Now for `x=1`, `2^x = 2` again due to the different numbers of digits, `2` can not be created from `23`.
3. Now for `x=2`, `2^x = 4` again due to the different numbers of digits, `4` can not be created from `23`.
4. Now for `x=3`, `2^x = 8` again due to the different numbers of digits, `8` can not be created from `23`.
5. Now for `x=4`, `2^x = 16` now the number of digits are same, but the frequency of digits in `16` and `23` are not the same so `16` can not be created from `23`.
6. Now for `x=5`, `2^x = 32` now number of digits are same, and frequency of digits in `32` and `23` are same `(2 => once, 3=> once)` so `32` can be created from `23`, return `true`.

## Implementation

C++ Code:

``````class Solution {
public:
bool reorderedPowerOf2(int N) {
int d = getNumOfDigits(N);
int a[10]={0};
getDigitsFreq(N,a);
int n2=1;
int d1;
for(int i=0; i<30; i++){
d1 = getNumOfDigits(n2);
if(d==d1){
int a1[10]={0};
getDigitsFreq(n2,a1);
int j;
for(j=0;j<10;j++){
if(a[j] != a1[j]){
break;
}
}
if(j==10){
return true;
}
}
else if(d<d1){
break;
}
n2=n2<<1;
}
return false;
}

void getDigitsFreq(int N, int a[]){
while(N){
a[N%10]++;
N /= 10;
}
}

int getNumOfDigits(int n){
int i=0;
while(n){
i++;
n /= 10;
}
return i;
}
};
``````

Runnable C++ code:

Cover Photo by Arnold Francisca on Unsplash