It should be sufficient to just count contribution of each bit into the answer separately.

Geometric progression sum with binary exponentiation

just off topic: It was on-campus or off-campus?

Just count number of set bits for each position(bit) in A to B and same for C to D. Then ans is just contribution of each bit ie. For each bit contribution is ((no. of set bits in A-B)*(no. of unset C-D)+(no. of set bits in C-D)*(no. of unset A-B))*(2^position). Hope this helps.

pastebin link code if u want, (not thoroughly tested).

wow i didnt know that taxi drivers should be good at cp nowadays, what a great time we live in!

This problem ultimately reduces to "Find number of setbits of ith bit for numbers between range x to y"

To find this there is a pattern, run this prog you will understand https://ideone.com/vMaCNs

its damn easy.i did a similar problem.just store the number of ones and zeros in both ranges.then just iterate over the 42 bits and pick zero from one set(a-b)and one from another and vice-versa.then multiply with 2^i(0-based index)using fast expo and sum it.and you get your answer

Coding round for interships or coding round for full-time ?? @D_Coder_03

• As the constraints are enormous we have to do something with bits
• First thought after this is to calculate every possible pair.
• If we can find the total no.s between A and B with 1 at a particular place we can solve the question
• Now we have no idea how to do that so we can take some examples
• So first 15 digits are

1000  
0100  
1100  
0010  
1010  
0110  
1110  
0001  
1001  
0101   
1101   
0011  
1011  
0111  
1111

• Now we will find total no.s from 1 to 15 with ith bit zero
• there are (1<<i)-1 no of zeroes at ith place before the start of the pattern
• Length of the pattern is (1<<(i+1)) for every place
• so total zeroes after pattern starts is ((length of pattern) / 2) * total_no_of_complete_pattern + zeroes from a partial pattern that may of may not form at the end
• total_no_of_complete_pattern (N)= (15 — ((1<<i) — 1) ) / ( 1<<i+1 ) now we can calculate the 1 part for 2 part we have a partial pattern of length (L) = ( 15 — ((1<<i) — 1) ) % ( 1<<i+1 ) now we can find no. of zeroes from it with simple if else

Hi Everyone, please I want a verification for my method or point out if I am wrong. let $$$A_1,A_2...A_k$$$ are the numbers in range $$$[A,B]$$$ and similarly let $$$C_1,C_2...C_m$$$ are the numbers in range $$$[C,D]$$$ so basically I have to calculate $$$\displaystyle \sum\limits_{i = 1}^k\displaystyle \sum\limits_{j = 1}^m A_i \,xor\,C_j $$$. but we know that $$$A_i \,xor\,C_j=(A_i +C_j)-2(A_i\,and\,C_j)$$$ also we know that $$$A\,and\,B+A\,and\,B=A\,and\,(B+C)$$$. Now let $$$\displaystyle \sum\limits_{j = 1}^mC_j=S_1$$$. So our inner summation $$$\displaystyle \sum\limits_{j = 1}^m A_i \,xor\,C_j $$$ becomes $$$mA_i+S_1-2(A_i\,and\,S_1)$$$. Now let $$$\displaystyle \sum\limits_{i= 1}^kA_i=S_2$$$. So $$$\displaystyle \sum\limits_{i = 1}^k (mA_i+S_1-2(A_i\,and\,S_1))$$$ is our final answer and it equals $$$m*S_2+k*S_1-2*(S_1\,and\,S_2).$$$ Since we can find $$$S_1,S_2$$$ in constant time so time complexity is $$$O(1).$$$ Please point out anyone if I am wrong.

Sorry,I didn't see the operator.Its exor I thought its addition. Pls don't read Try using prefix sum.Time complexity=O(n). Create a array of length=max_sum you can achieve+1 say the name of array is arr Initialize it with zeros Then run a loop from A to B: arr[i+C]+=1 arr[i+D+1]-=1 Then run a loop on array and perform arr[i]+=arr[i-1] Create a new var ans=0 now again iterate arr: and do ans+=arr[i]*i

For each integer in range, a to b and range c to d find the number of integers having i-th (0 <= i <= 30) bit set and unset.

Let c11 denoted the count of integers in range a to b having i-th bit set. Then c12 = (b-a+1-c11) integers are having bits unset in this range.

Similarly, let c21 denoted the count of integers in range c to d having i-th bit set. Then c22 = (d-c+1-c21) integers are having bits unset in this range.

Now for each i-th bit in range (0,30). Add to answer the value equals ((c11*c22 + c12*c21) % mod) *(1LL<<i)) % mod where mod = 1e9+7.

#define mod 1000000007
#define ll long long int

long long getcount(long long n, int k)
{
    long long res = (n >> (k + 1)) << k;
    if ((n >> k) & 1)
        res += n & ((1ll << k) - 1);
    return res;
}

void solution(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    assert(a>=1 && a<=b);
    assert(b>=a && b<=1000000000);
    assert(c>=1 && c<=d);
    assert(d>=c && d<=1000000000);
    ll t1 = b-a+1;
    ll t2 = d-c+1;
    ll res=0;
    for(ll i=0;i<31;++i){
        ll c1 = getcount(b+1,i)-getcount(a,i);
        ll c2 = getcount(d+1,i)-getcount(c,i);
        // set + unset
        ll cnt = c1*(t2-c2);
        cnt %= mod;
        res += ((1LL<<i)*cnt)%mod;
        res %= mod;
        // unset + set
        cnt = (t1-c1)*c2;
        cnt %= mod;
        res += ((1LL<<i)*cnt)%mod;
        res %= mod;
    }
    assert(res>=0);
    cout<<res<<endl;
}

Reference GFG article: Count integers up to N having K-th bit set in O(1)

Hello! Is there any way to check the code approach to this problem?

Here is my approach for the problem:

Note considering the MOD part in the code (that can be included if required)

#include <bits/stdc++.h>
using namespace std;
#define int long long

// return the count of number of 1's at ith bit in a range [1, n]
long long getcount(long long n, int k)
{
	n++;
	long long res = (n >> (k + 1)) << k;
	if ((n >> k) & 1) res += n & ((1ll << k) - 1);
	return res;
}

signed main()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int num1 = b - a + 1;
    int num2 = d - c + 1;
    int bit_count_outer[64], bit_count_inner[64];
    for(int i = 0; i <= 63; i++){
        bit_count_outer[i] = getcount(b, i) - getcount(a-1, i);
    }
    for(int i = 0; i <= 63; i++){
        bit_count_inner[i] = getcount(d, i) - getcount(c-1, i);
    }
    int sum = 0;
    int contrib = 1;
	for(int i = 0; i <= 63; i++){
	    int outer_one_count = bit_count_outer[i];
	    int outer_zero_count = num1 - outer_one_count;
	    int inner_one_count = bit_count_inner[i];
	    int inner_zero_count = num2 - inner_one_count;
	    int sum1 = (outer_one_count * inner_zero_count) + (outer_zero_count * inner_one_count);
	    sum +=  contrib * sum1;
	    contrib *= 2;
	}
	cout << "The sum is: " << sum << endl;
	return 0;
}