 # PROBLEM LINK:

Practice

Contest

Author: Praji Benerjee

Tester: Md Shahid

Editorialist: Md Shahid

Cakewalk

Bits

# PROBLEM:

Given any positive number N and you need to find total number of unset bits

# EXPLANATION:

This problem is very easy. First of all convert the number N into string of binary numbers( 0 or 1). Now count the number of zeros from binary form. For example, you have number N=10, binary form of this number will be S="1010", now count number of zeros i.e, 2 so answer will be 2.

## Time Complexity :

Converting a decimal number into binary takes O(logN) time.

# SOLUTIONS:

Author's Solution
``````#include<bits/stdc++.h>
#define int long long int
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

signed main(){
fast
int t ;cin>>t;
while(t--){
int n; cin>>n;
int ans=__builtin_popcount(n);
int total=(int)log2(n)+1;
int nigga=total-ans;
cout<<nigga<<endl;
}
return 0;
}
``````
Tester & Editorialist Solution
``````for _ in range(int(input())):
N = int(input())
b = bin(N)
print(b.count('0')-1)
``````

All the suggestions are welcome.

1 Like

Why complexity is O(logn)…

As you can see, you have to convert a number to its binary form. It takes at least O(logN) time.

No __builtin_popcount take 1 complexity

Complexity of __builtin_popcount is O(number of bits) and maximum number of bits here will be 59 for 10^{18} at most so you can say that it is taking almost constant time to find answer.

Yeah…
That’s what I want to say…??
Where is editorial of lcm and gcd question with extended version?