Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Power Of 2

Last Updated on March 22, 2022 by Ria Pathak

Concepts Used

Strings, Mathematics

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` – 1020

Efficient Approach :

As a larger number cannot be taken as an integer, we take input as a string.

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));
}

}
}

```
```for _ in range(int(input())):

a = list(input())

if len(a) == 0:
print(0)
continue

if len(a) == 1 and a[0] == "1":
print(0)
continue

else:
n = 0
len_ = len(a)
c = 0

while len_ != 1 and a[len_ - 1] != 1:

if int(a[len_ - 1]) % 2 != 0:

print(0)
c = 1
break

j = 0

for i in range(len_):

n = n*10 + int(a[i])

if n<2:

if i != 0:

a[j] = "0"
j += 1

continue

z = n//2
a[j] = str(z) + "0"
j += 1
n = n - (n//2)*2

a[j] = "\0"
len_ = j

if int(a[0]) % 2 == 0 and c == 0:
print(1)

elif c == 0:
print(0)