For a given integer 'N', you have to return the number of set bits in the binary representation of the numbers from 1 to 'N'.
In a binary number '1' is considered as a set bit and '0' as not set.
If 'N' is 4, then
1 has a binary representation of 1
2 has a binary representation of 10
3 has a binary representation of 11
4 has a binary representation of 100
Hence number of set bits is 5.
The first line contains a single integer which is 'N'
Count of set bits from 1 to 'N' is printed on the first line.
7
12
1 has a binary representation of 1
2 has a binary representation of 10
3 has a binary representation of 11
4 has a binary representation of 100
5 has a binary representation of 101
6 has a binary representation of 110
7 has a binary representation of 111
Hence number of set bits is 12.
5
7
1 <= N <= 10^9
Try to find a pattern in the bitwise representation of 1 to N.
Considering the range from 1 to N is equivalent to the range from 0 to N, we can analyze the count of set bits by examining each bit position individually.
When counting the set bits from 0 to N in the binary representation of numbers, we can observe a repeating pattern at the units place. The pattern consists of a window size of 2, with the sequence "01" repeating. At the next place, the window size doubles to 4, and the pattern becomes "0011". This pattern continues for each subsequent bit position.
0000 -> 0
0001 -> 1
0010 -> 2
0011 -> 3
0100 -> 4
0101 -> 5
0110 -> 6
0111 -> 7
1000 -> 8
1001 -> 9
1010 -> 10
To calculate the count of set bits for the complete repetitions of the window, we multiply the number of complete repetitions, which is (N+1)/d, by the count of set bits in each repetition, which is d/2. This gives us ((N+1)/d)*(d/2) set bits from the complete repetitions.
For the remaining part, which is (N+1)%d, we know that the first d/2 bits are always zeros. To obtain the count of set bits in the remaining part, we subtract d/2 from (N+1)%d. However, if (N+1)%d is less than d/2, it results in a negative number. To avoid this, we take the maximum of ((N+1)%d - d/2) and 0, ensuring a non-negative count.
By applying this calculation process from the least significant bit to the most significant bit, starting with a window size of 2 and doubling it at each step, we can efficiently count the set bits in the binary representation of numbers from 0 to N.
1. Start with the input number N and initialize variables:
Enter a loop that continues until the value of x becomes zero:
Return the final count of set bits stored in ans.
O(log(N)), where ‘N’ is the given input.
We are performing an addition for every bit in the binary representation of N which is log(N). Hence Time Complexity O(log(N)).
O(1)
We are not using any extra space, thus the constant space complexity.
All tags
Sort by
Interview problems
C++ || Easy
int findMSB(int n) {
int x = 0;
while(n) {
n = n >> 1;
x++;
}
return x;
}
int fun(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
int msb = findMSB(n);
long long x = (pow(2, msb - 1) * (msb - 1))/2;
long long excludingMSB = (n & (~(1 << (msb - 1))));
return x + excludingMSB + 1 + fun(excludingMSB);
}
int countSetBits(int n)
{
return fun(n);
}Interview problems
one testcase is showing TLE can someone solve it????
int countSetBits(int N)
{
//Write your code here
long long cnt = 0;
for(long long i=1; i<=N; i++)
{
long long tem = i;
while(tem >= 1)
{
if(tem%2 == 1)
{
cnt++;
}
tem = tem/2;
}
}
return cnt;
}
Interview problems
optimal
int gethigher2power(int n){
int x=0;
while((1<<x)<=n){
x++;
}
return x-1;
}
int slove(int n){
if(n==0) return 0;
//Write your code here
int x=gethigher2power(n);
int less2power=x*(1<<(x-1));
int msbbits=n-(1<<x)+1;
int rem=n-(1<<x);
int ans=less2power+msbbits+slove(rem);
return ans;
}
int countSetBits(int n)
{
return slove(n);
}
Interview problems
Easy solution though failing at last case
#include<bitset>
int countSetBits(int N)
{
int c=0;
for(int i=1;i<=N;i++)
c+=__builtin_popcount(i);
return c;
}
Interview problems
Can Somebody explain why I got TLE for this code? Please
int countSetBits(int N)
{
int count = 0;
for(int i=0;i<=N;i++){
while(i > 0){
if ((i & 1) != 0) {
count++;
}
i = i >> 1;
}
}
return count;
}
Interview problems
The Approach were bit hard and on Observation . So dont go for it Only learn the direct Formula of this (2^p-1)*p+(n-2^p+1)+call same function of Smaller Input.Here P stands for Most Significant bit (Highest 2 Power)of n which is Set.
int f1(int n){
if(n==0)return 0;
int p=0;
while(n>=(1<<p)){
p++;
}
p-=1;
return ((1<<p-1)*p+(n-(1<<p)+1)+f1(n-(1<<p)));
}
int countSetBits(int N)
{
//Write your code here
return f1(N);
}
Interview problems
Recursive Approach(Failing for large Test Cases though)
int countSetBits(int N)
{
//Write your code here
if(N==1) return 1;
int cnt = countSetBits(N-1);
while(N!=0)
{
N = ((N)&(N-1));
cnt++;
}
return cnt;
}
Interview problems
TLE for most optimal code.
Even though my code is optimal, i still am getting TLE issues. Can any one spot any mistake in either of the apporaches?
public class Solution{
public static int getSetBitsBrute(int n){
int ans = 0;
while(n != 0){
if((n & 1) == 1) ans++;
n = n >> 1;
}
return ans;
}
public static int getSetBitsOptimal(int n){
int ans = 0;
while(n != 0){
n = (n & (n -1));
ans++;
}
return ans;
}
public static int countSetBits(int n) {
//Write your code here
int ans = 0;
for(int i = 1; i <= n; i++){
// ans += getSetBitsBrute(i);
ans += getSetBitsOptimal(i);
}
return ans;
}
}Interview problems
#ONLY POSTED C++ EFFICIENT SOL.
#include <vector>
using namespace std;
int countSetBits(int N) {
int count = 0;
for (int i = 1; i <= N; i <<= 1) {
int k = (N + 1) / (i << 1);
count += k * i;
int remainder = (N + 1) % (i << 1);
if (remainder > i)
count += remainder - i;
}
return count;
}
Interview problems
Recursive C++ Solution using BIT Manipulation
int largestPowerOfTwoTillN(int N){
int x=0;
while((1<<x) <=N){
x++;
}
return x-1;
}
int countSetBits(int N)
{
//Write your code here
// int setBits=0;
// for(int i=1;i<=N;i++){
// int n=i;
// while(n>0){
// n = n&(n-1);
// setBits++;
// }
// }
// return setBits;
if(N==0) return 0 ;
int x = largestPowerOfTwoTillN(N);
int noOfSetBitsTillX = (1<<(x-1))*x;// 2^x-1 * x
int noOfSetBitsInMSBafterX = N - (1<<x)+1;
int rest = N-(1<<x);
int ans = noOfSetBitsTillX+noOfSetBitsInMSBafterX+ countSetBits(rest);
return ans;
}