Power Of 2

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
8 upvotes
Asked in companies
GoogleCIS - Cyber InfrastructureInfosys

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.
Detailed explanation ( Input/output format, Notes, Images )

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
Sample Input 1 :
2
100
218
Sample Output 1 :
0
1
Explanation of Sample Input 1 :
For the first test case :  
All the possible combinations of 100 start with 0, which is not allowed, and the only permutation where it starts with 1 is 100, which is not a power of 2. Therefore, the answer is false.

For the second test case :
Then the answer will be true because it can be rearranged to 128, which is 2 raised to the power of 7.
Sample Input 2 :
2
46
1
Sample Output 2 :
1
1
Hint

Can we try all permutations? 

Approaches (2)
Trying all permutations

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.
Time Complexity

O(log(N)!), where N is the number given. 

 

For a given number N, it contains log(N) digits, and we are trying all possible permutations, therefore log(N)! permutations exist. Therefore the net time complexity is O(log(N)!).

Space Complexity

O(log(N)), where N is the number given.

 

Since we are using a string to store the number and contains at max log(N) digits.

Code Solution
(100% EXP penalty)
Power Of 2
Full screen
Console