HitBit Editorial

Problem Link :

Contest : https://www.codechef.com/CYPH2016/problems/HITBIT

Practice : https://www.codechef.com/problems/HITBIT

Author : Atul Mishra

Tester : Abhinesh Garhwal

Editorialist : Atul Mishra

Difficulty :
Cakewalk

Prerequisites :
Bit Manipulation

Problem :
Sum of all the numbers from range(l,r) whose kth bit is set.

Quick Explanation :
Check the kth bit and add.

Explanation:
The problem can be solved by multiple ways :

Method 1:

Given a range(1,10), convert each number into its binary equivalent and check the kth bit. one can convert a number directly to its binary representation through using bitset.

Code :

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int main()
    {  
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{
          ll l,r,k;
          scanf("%lld %lld %lld",&l,&r,&k);
          ll sum=0;
          for (int i = l;i<=r; i++)
          {
          	bitset<32> arr(i);
          	if(arr[k-1]==1)
          		sum=sum+i;
	
          }
	
          printf("%lld\n",sum);
    	}
    	
    }   

Method 2:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;


int main(){

int tc;
scanf("%d",&tc);
while(tc--)
{
    ll l,r;
    int k;
    scanf("%lld %lld %d",&l,&r,&k);
    k--;
    ll j = 1<<k; //shift k bit left j
    ll sum=0;
    for(ll i=l;i<=r;i++)
    {
        ll res = i & j; //i AND j
        if(res==j)
        {
            sum+=i;
        }
    }
    printf("%lld\n",sum);
}

return 0;

}

I don’t think O(n) approach can pass the test case where the constraints are 1 < l,r < 10e9??Right?

Yes, it do passes the test cases

//