Leetcode 869. Reordered Power of 2 [Solution]
Tags: cpp, algorithms, programming, tutorial
Published: 2021-03-21 16:02:34

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

**Difficulty:** Medium
**Jump To:**
* [Problem Statement](#problem-statement)
* [Explanation](#explanation)
* [Solution](#solution)
* [Implementation](#implementation)

---

## Problem Statement <a name="problem-statement"></a>

**Question:** [https://leetcode.com/problems/reordered-power-of-2/](https://leetcode.com/problems/reordered-power-of-2/)


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 <a name="explanation"></a>

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 <a name="solution"></a>

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 <a name="implementation"></a>

**C++ Code:**

```cpp
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:**

{% replit @shivams136/Leetcode-869-Reordered-Power-of-2 %}

Cover Photo by [Arnold Francisca](https://unsplash.com/@clark_fransa?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](/s/photos/code?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)