PROBLEM LINK: Click here
Contest: Hey Newbees, Here is Some Honey -ROUND 3
Author: Arefin Labib
Co-Author: Samia Rahman
Tester: Sanjida Akter
Tester: Redowan Ibrahim
Tester: Nazmus Sakib
Editorialist: Samia Rahman
DIFFICULTY:
Simple
PREREQUISITES:
Number theory
PROBLEM:
You will be given a positive integer N.
You have to figure it out how many integer numbers from 1 to N are not polite numbers.
Now what is polite numbers?
EXPLANATION:
If a positive integer can be represent as the sum of two or more consecutive positive integers then it’s a polite number. It can be proved that, only the numbers which are power of 2 is a non polite number. Click here for explanation.
Short Explanation: ans =log2(n) +1
TIME COMPLEXITY:
O(log n)
SOLUTIONS:
C++
//BISMILLAHIR RAHMANIR RAHIM
#include<bits/stdc++.h>
#define ll long long
#define __ <<" "<<
#define FastRead \
ios_base::sync_with_stdio(false); \
cin.tie(0);
#define loop(m,n) for(m=0;m<n;m++)
#define loop1(p,q) for(p=1;p<=q;p++)
#define sf(T) scanf("%lld",&T)
#define ssf(T) scanf("%s", T)
#define pf(T) printf("%lld ",T)
#define rloop1(p,q) for(p=q;p>0;p--)
#define rloop(m,n) for(m=n-1;m>=0;m--)
#define case(z) cout<<"Case " << z++ << ": "
#define ptf(b) puts(b?"Yes":"No")
#define newline cout<<endl
#define bye return 0
using namespace std;
int main()
{
FastRead
//freopen("ain.txt","r",stdin);
//freopen("aoutt.txt","w",stdout);
ll i,j;
ll Tc,l=1;
cin>>Tc;
while(Tc--)
{
long long int n,ans;
cin>>n;
ans = log2(n);
cout<<ans+1<<endl;
}
bye;
}