 # SUM2POW | Special Number 2 | Editorial

## Editorial

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

## 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