PROBLEM LINK:
PRACTICE
Editorialist: Avishake Maji
DIFFICULTY:
MEDIUM
PREREQUISITES:
Number Theory
PROBLEM:
You are given a number X. You have to tell the count of number that are power of two. If a number is in the power of two, check for that number as well. Let X=2, we know 2 is a power of 2 and its power is 1. 1is also a power of 2 and its power is 0. So 1 is the only number which can be represented as a power of 2(2^1=2) and it is also in the power of 2(2^0=1). Note: Here we don’t consider 2.
Input:
t: Number of test cases
X: An given number
Output:
The number of power of 2’s which is a power of 2
Constraints:
1<=t<=1000
1<=X<=10^6
Sample Input:
2
3
16
Sample Output:
0
3
Explanation:
Since 3 is not power of 2 so the answer is 0
16 is a power of 2. Its power is 4. 4 is a power of 2. Its power is 2. 2 is also a power of 2. Its power is 1.1 is also a power of 2. Its power is 0. Now 0 is not a power of 2. Since 4,2,1 are power of 2 therefore the answer is 3.
EXPLANATION:
Here in this question we are told to find the number of 2 which is indeed in the power of 2. To solve this problem we will take the help of log in the base 2. If the given number is not in the power of 2 we will print 0. If the given number is in the power of 2 but if its power is not in the power of 2 then we will return 0 else we will use a while loop and keep on checking whether the power of 2 is in the power of 2 or not. If yes we will increment the counter by 1.
SOLUTION:
#include <iostream>
#include<cmath>
#include<ctime>
#include<map>
#define ll long long int
using namespace std;
void solve();
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("error.txt", "w", stderr);
// freopen("output.txt", "w", stdout);
// #endif
int t;
/*is Single Test case?*/ cin >> t;
while (t--) {
solve();
// cout << "\n";
}
// cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
return 0;
}
void solve()
{
ll n;
cin>>n;
if((ll)log2(n)==log2(n)&&(ll)log2(log2(n))==log2(log2(n))){
ll c=0;
n=log2(n);
while(n!=0&&(ll)(log2(n))==log2(n))
{
c++;
n=log2(n);
}
cout<<c<<endl;
}
else
cout<<"0"<<endl;
}