#### Concepts Used

Strings, Mathematics

#### Difficulty Level

Hard

#### Problem Statement (Simplified):

Find if the number given as a string is the power of two or not. Return 1 if yes, else 0.

**See original problem statement here**

#### Test Case

```
Input:
2
16
99
Output:
1
0
Explanation:
Case-1:
16 can be represented as 2^4, hence it is a power of two, so we print 1.
Case-2:
99 is not a power of two, we print 1.
```

#### Solving Approach :

Bruteforce Approach:

1) Convert string number into an integer or long long int.

2) Check if the number is the power of two by dividing it by 2 repeatedly.

3) This Approach is only suitable for numbers of length`1`

– 10^{20}

Efficient Approach :

1) As a larger number cannot be taken as an integer, we take input as a string by referrring certain websites to learn coding.

1)We first check if the string is a single digit and have value 1 or not, if yes we return 0 because we need to check if the number is the power of 2 greater than 1.

2) If that condition fails, we divide the string by 2 repeatedly using the conventional method of digit by digit division until we get a value 1 or any odd number.

3) If the number becomes odd in the procedure we return 0 and get out of the loop. Else we continuously divide.

4) After the loop, if we receive 1 that means the number was the power of two and after continuous division only 1 is left. So we return 1.

## Example

- Let’s take
`32`

as an example here:

Step-1, Number = 32 :

Last index have an even number, so we can move on two next step.

We divide this number character by character.

`3`

at index is odd and on division gives`1`

as quotient and also`1`

as remainder, so we replace current value in string by quotient, and carry remainder to next value.

`2`

at index is even, but we have an carry (`1`

) from last digit, so we add`10`

to current value. Current value becomes`12`

, so we divide it now by`2`

,no remainder is carried. Quotient`12/2`

i.e.`6`

replaces the current value. So, current value becomes`6`

.So after, first division, our number becomes

`16`

.

Step-2, Number = 16 :Last index have an even number, so we can move on two next step.

We again divide this number character by character.

`1`

at current index is less than`2`

, so it will be taken as carry to next digit. Also, we replace current character by`0`

.

`6`

at current index is divisible by`2`

, but we also have a`1`

as carry from the last digit, so we add`10`

to the current value, making it`16`

. We then replace current character by Quotient`16/2`

i.e.`8`

, hence our final number becomes`08`

. We drop`0`

from the start as it will have no significance.

Step-3, Number = 8 :Last index have an even number, so we can move on two next step.

We again divide this number character by character.

Last index have an even number, so we can move on two next step.

`8`

at current index is divisible by`2`

also we don’t have any carry. So, We replace current character by Quotient`8/2`

i.e.`4`

, hence our final number becomes`4`

.

Step-4, Number = 4 :Last index have an even number, so we can move on two next step.

We again divide this number character by character.

`4`

at current index is divisible by`2`

also we don’t have any carry. So, We replace current character by Quotient`4/2`

i.e.`2`

, hence our final number becomes`2`

.

Step-5, Number = 2 :Last index have an even number, so we can move on two next step.

We again divide this number character by character.

`2`

at current index is divisible by`2`

also we don’t have any carry. So, We replace current character by Quotient`2/2`

i.e.`1`

, hence our final number becomes`1`

.

Final step:

As we can see our string has a length of

`1`

now, so we check if the last digit is`1`

or not. If yes, given value was the power of`2`

, else it is not.Given number has

`1`

in last, so given number was a power of two, so we print`1`

as answer.## Solutions

#include <stdio.h> int main() { int tes; scanf("%d", &tes); while(tes--){ char A[1001]; scanf("%s", A); if(strlen(A)==0){ printf("0\n");continue; } if(strlen(A)==1 && A[0] == '1'){ printf("0\n");continue; } else{ int n = 0; int len = strlen(A); int i,j,c=0; while(len !=1 &&A[len-1] != 1) { if((A[len-1]-'0')%2 != 0) { printf("0\n"); c=1; break; } for(i=0, j=0; i<len; i++) { n = n*10 + (A[i]-'0'); if(n<2) { if(i!=0) A[j++]= '0'; continue; } A[j++] = (int)(n/2) +'0'; n = n - (n/2) * 2; } A[j] = '\0'; len = j; } if((A[0]-'0')%2 == 0 && c==0) printf("1\n"); else if(c==0) printf("0\n"); } } }#include <bits/stdc++.h> using namespace std; int main() { int tes; cin>>tes; while(tes--){ string A; cin>>A; if(A.size()==0){ cout<< 0<<endl;continue; } if(A.size()==1 && A[0] == '1'){ cout<<0<<endl;continue; } else{ int n = 0; int len = A.size(); int i,j,c=0; while(len !=1 &&A[len-1] != 1) { if((A[len-1]-'0')%2 != 0) { cout<<0<<endl; c=1; break; } for(i=0, j=0; i<len; i++) { n = n*10 + (A[i]-'0'); if(n<2) { if(i!=0) A[j++]= '0'; continue; } A[j++] = (int)(n/2) +'0'; n = n - (n/2) * 2; } A[j] = '\0'; len = j; } if((A[0]-'0')%2 == 0 && c==0) cout<<1<<endl; else if(c==0) cout<<0<<endl; } } }import java.util.*; import java.io.*; public class Main { public static int calc(String s){ int len = s.length(); if(((int)s.charAt(s.length() - 1)-(int)('0'))%2!=0) return 0; int carry=0; while(len!=1){ if(((int)s.charAt(s.length()-1)-(int)('0'))%2!=0) return 0; for(int i=0; i<len;i++){ int curr = 10*carry + (int)s.charAt(i) - (int)('0'); carry = curr%2; s = s.substring(0,i) + (char)((curr/2)+(int)('0')) + s.substring(i+1); } if(s.charAt(0)=='0'){ s = s.substring(1); len--; } } if(s.charAt(0)=='1' || s.charAt(0)=='2' || s.charAt(0)=='4' || s.charAt(0)=='8') return 1; else return 0; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int tes = sc.nextInt(); while(tes--!=0){ String A = sc.next(); System.out.println(calc(A)); } } }

### Time Complexity

O(N

^{2})

### Space Complexity

O(1)