Power Of 2

Last Updated on March 22, 2022 by Ria Pathak

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²⁰

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)
# your code goes here

Time Complexity

O(N²)

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.