Last Updated: 12 Apr, 2021

Power Of 2

Moderate

Asked in companies

Solve now

Problem statement

You are given an integer ‘N’. We can 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 so that the resulting number is a power of two. Else, return false.

For Example :

Given :-
‘N’ = 218
Then the answer will be true because it can be rearranged to 128, which is 2 raised to the power of 7.

Input Format :

The first line of input contains an integer ‘T’ denoting the number of test cases.

The next ‘T’ lines of the test case contain exactly one integer, ‘N’ the number given to us.

Output Format :

For each test case, print 1 or 0 depicting if it is possible or impossible to rearrange the given number as a power of 2, respectively.

The output of each test case will be printed in a separate line.

Note :

You don't have to print anything; It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
0 <= N <= 10 ^ 9

Time limit: 1 sec

Solve now

Approaches

01 Approach

The main idea is to convert ‘N’ to a string ‘S’ and sort its characters. Then for all possible permutations, check if the current permutation is a power of 2.

Convert the number ‘N’ into a string ‘S’.
Sort the characters of string ‘S’ in ascending order, which is the default order of the sort function.
Try all possible permutations of the ‘S,’ and for every permutation, we check if it is a power of 2 by calling a ‘HELPER’ function.
The HELPER function:
- Takes the string ‘S’ as an input parameter.
- Converts ‘S’ back to integer ‘NUM.’
- Count the number of set bits in ‘NUM’.
- If the set bit is precisely 1, return true.
- Else return false.
If any permutation of ‘S’ was not the power of 2, return false.

Solve now

02 Approach

The main idea is to create a frequency table, ‘COUNT_ARRAY’, of the number ‘N’, which stores the frequency of each digit in the number. Then for every power 2 in the range of 1 to 10 ^ 9, check if the ‘COUNT_ARRAY’ matches the frequency table of the current element.

Make a ‘COUNT_ARRAY’ using a helper function ‘COUNT’.
The function ‘COUNT’:
- Takes an integer ‘N’ as input.
- Makes a frequency table ‘ARR’.
- ‘ARR’ stores the frequency of each digit in ‘N’.
- Return ‘ARR’.
Loop ‘I’ from 0 to 30 and check if for (1 << i) are both the ‘COUNT_ARRAY’ and ‘COUNT(1<<i)’ equal.
If they are equal, return true.
Else if no match is found, return false.

Solve now