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:
Case1:
16 can be represented as 2^4, hence it is a power of two, so we print 1.
Case2:
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 length1
– 10^{20}
Efficient Approach :
As a larger number cannot be taken as an integer, we take input as a string.

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.

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.

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

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:Step1, 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 gives1
as quotient and also1
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 add10
to current value. Current value becomes12
, so we divide it now by2
,no remainder is carried. Quotient12/2
i.e.6
replaces the current value. So, current value becomes6
.So after, first division, our number becomes
16
.Step2, 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 than2
, so it will be taken as carry to next digit. Also, we replace current character by0
.
6
at current index is divisible by2
, but we also have a1
as carry from the last digit, so we add10
to the current value, making it16
. We then replace current character by Quotient16/2
i.e.8
, hence our final number becomes08
. We drop0
from the start as it will have no significance.Step3, 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 by2
also we don’t have any carry. So, We replace current character by Quotient8/2
i.e.4
, hence our final number becomes4
.Step4, 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 by2
also we don’t have any carry. So, We replace current character by Quotient4/2
i.e.2
, hence our final number becomes2
.Step5, 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 by2
also we don’t have any carry. So, We replace current character by Quotient2/2
i.e.1
, hence our final number becomes1
.Final step:
As we can see our string has a length of
1
now, so we check if the last digit is1
or not. If yes, given value was the power of2
, else it is not.Given number has
1
in last, so given number was a power of two, so we print1
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[len1] != 1) { if((A[len1]'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[len1] != 1) { if((A[len1]'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) # your code goes here
Time Complexity
O(N^{2})
Space Complexity
O(1)
This article tried to discuss the concept of Strings, Mathematics. Hope this blog helps you understand and solve the problem. To practice more problems on Strings, Mathematics you can check out MYCODE  Competitive Programming.