SUM2POW | Special Number 2 | Editorial

editorial
1

Editorial

Problem Link

Setter: Sidharth Sethi
Tester: Sidharth Sethi
Editorial: Nikhil

Problem Statement:
Rajan is fond of special numbers. According to him a number is special if the sum of all digits of number N is a power of 2. Can you help him tell whether a number is special or not?

INPUT
A test case T
Number N

OUTPUT
Single Line Output containing YES or NO

Test Constraints
1 <= T <= 100
0 <= N <= 2^31

SAMPLE INPUT
3
1
3
13

SAMPLE OUTPUT
YES
NO
YES

Explanation
TEST 1 - 1 is power of 2 at 0
TEST 2 - 3 isn’t a power of 2
TEST 3 - 13 which sums to 4 is power of 2 at 2

Approach

Task1 - Calculate the sum of all the digits in a number

Task2 - Check if sum is power of 2 or not .

Code (C++):

#include<bits/stdc++.h>
using namespace std;

// Different methods to check the power of 2
// Method 1 - using while loop
bool checkPowerof2(int n){ // Time : O(logN)
    while(n>1){
        if(n % 2 != 0)return false;
        n/=2;
    }
    return true;
}

// Method 2 -> using math
 bool checkPowerof2(int n){ // Time:  O(1)
     if(n == 0)return false;
     return (ceil(log2(n))) == (floor(log2(n))); 
 }

// Method 3 -> using bits
 bool checkPowerof2(int n){// Time : 0(1) -> Fastest among 3 
     return   n && (! (n & (n - 1)));
 }

int32_t main()
{
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        
        // count the sum of digits
        int sum = 0;
        while(n){
            sum += n % 10;
            n/=10;
        }

        // check if sum is power of 2 or not
        if(checkPowerof2(sum)){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }



    }
	return 0;
}

Time Complexity:

In this problem, overall time complexity depends on which algorithm we are using to check the sum of digits is power of 2.

  • If we use O(1) algorithms to check the power of 2, then it will take O(N) time, where N = number of digits in a number
  • If we use O(logN) algorithm to check the power of 2, then it will take
    O(max(N, log2(sum))), where N = number of digits in a number and sum = sum of all digits

Space complexity:
O(1) → we are not using any extra space