CODEWITHSUNDEEP
c++bit-manipulationbinary-search
Purushottam
Purushottam

Reputation: 159

Count of total Numbers With 3 set Bits only in a range

I recently come across a question , Question statement is like this :

For given value of L and R, We have to find the count of number X, which have only three-set bits in it's binary representation such that "L ≤ X ≤ R".

Expected Time Complexity: O(log(63^3))

Expected Auxiliary Space: O(1)

Link - https://practice.geeksforgeeks.org/problems/akku-and-binary-numbers0902/0/

I have tried this solution but it is showing to optimize more , any suggestion how I can optimize it

 long long solve(long long l, long long r){
        long long count = 0,ctr=0;
        for(long long j=l; j<=r; j++){
            count = 0;
            for(int i=31; i>=0; i--)
            {    if(j & (1<<i))
                   count++; 
                if(count>3) break; // If counts more than 3 set bits then break it
            }
            if(count==3)
                ctr++;
        }
        return ctr;
    }

Upvotes: 1

Views: 1328

Answers (2)

Prabhakar Yadav
Prabhakar Yadav

Reputation: 81

To solve this question without 3 loops, you can find pattern in bit-count.

Example :

                     //count of numbers having exactly x-setbits

    : 0 -> 00000000  //0-setBit = 1, 1-setBit = 0, 2-setBit = 0, 3-setBit = 0
--------------------------
2^0 : 1 -> 00000001  //0-setBit = 1, 1-setBit = 1, 2-setBit = 0, 3-setBit = 0
--------------------------
2^1 : 2 -> 00000010  
      3 -> 00000011  //0-setBit = 1, 1-setBit = 2, 2-setBit = 1, 3-setBit = 0
--------------------------
2^2 : 4 -> 00000100  
      5 -> 00000101
      6 -> 00000110
      7 -> 00000111  //0-setBit = 1, 1-setBit = 3, 2-setBit = 3, 3-setBit = 1
--------------------------
2^3 : 8 -> 00001000
      9 -> 00001001
     10 -> 00001010
     11 -> 00001011
     12 -> 00001100
     13 -> 00001101
     14 -> 00001110
     15 -> 00001111  //0-setBit = 1, 1-setBit = 4, 2-setBit = 6, 3-setBit = 4
--------------------------
2^n : .....

Now notice that each new container (enclosed with "-----") contains all the previous containers in sequence with 1 added in front of them.

Example :

  1. 2^2 container is made up of 0, 2^0, 2^1 containers with 1 added at third bit.
  2. 2^3 container is made up of 0, 2^0, 2^1, 2^2 containers with 1 added at fourth bit

Using this observation we notice that "every exactly x-setbits count = x-setbits + (x-1)-setbits(of prev container)" as current container is made up of prev container+1

Since we are only required to find exactly 3-setbits count we can further optimize this.

Notice:

  1. exactly 0-setbit count is always 1
  2. exactly 1-setbit count is n for containers less than 2^n if n >= 1 else 0 (sum of 1)
  3. exactly 2-setbit count is n(n-1)/2 for containers less than 2^n if n >= 2 else 0 (sum of n)
  4. exactly 3-setbit count is n(n-1)(n-2)/6 for containers less than 2^n if n >= 3 else 0 (sum of sum of n)

=> we can compute required values of all containers less than 2^n in O(1).

Now, given problem can be broken down as:

Count of exactly 3-setbit in range [L,R] == Count in range [0,R] - Count in range [0,L-1]

Code:

long long compute(long long n,long long k){
    switch(k){
        case 1 : return n < 1 ? 0 : n;
        case 2 : return n < 2 ? 0 : n*(n-1)/2;
        case 3 : return n < 3 ? 0 : n*(n-1)*(n-2)/6;
    }
    return -1;
}

long long cal(long long val,long long k){
    if(k == 0)return 1;
    if(val == 0)return 0;
    long long n = log2(val);

    long long res = compute(n,k) + cal(val-(1LL<<n),k-1);
    return res;
}


long long solve(long long l, long long r){
    return cal(r,3) - cal(l-1,3);
}

Complexity:

  • Time Complexity: O(log(n))
  • Space Complexity: O(1)

This solution is working for the link which is provided in the question

Upvotes: 1

Paurush Batish
Paurush Batish

Reputation: 56

The idea behind the code is fairly simple. We generate binary numbers by taking set bits. In this question three set bits have been asked, so we will make three variables and run three while loops.

For example, numbers are asked --> 11 to 19

  • we take i = 1 j = 2, k = 4 and start the loops. We make temp as OR of - i j and k. For example when representing in binary
  • 1 = 0001
  • 2 = 0010
  • 4 = 0100

OR = 0111 --> 7 , Hence if the number is in the range [l,r] the count is increased.

Code by --> https://auth.geeksforgeeks.org/user/628826/practice/

long long solve(long long l, long long r){

    long long i = 1;
    long long cnt = 0;
    while (i < r)
    {
        long long j = i << 1;
        while (j < r)
        {
            long long k = j << 1;
            while (k < r)
            {
                long long tmp = i | j | k;
                //cout<<i<<" "<<j<<" "<<k<<" "<<tmp<<endl;
                if (l <= tmp && tmp <= r)
                    ++ cnt;
                k <<= 1;
            }
            j <<= 1;
        }
        i <<= 1;
    }
    
    return cnt;
    
}

Upvotes: 4

Related Questions