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
Jump To:

• Problem Statement
• Explanation
• Solution
• Implementation

Problem Statement

Question: 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

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