PROBLEM LINK:
Setter: Yusuf Kharodawala
Tester: Radoslav Dimitrov
Editorialist: Raja Vardhan Reddy
DIFFICULTY:
Easy
PREREQUISITES:
Bit operations.
PROBLEM:
You are given positive integers L and R. You have to find the sum
S=∑_{i=L}^{i<=R}(L∧(L+1)∧…∧i),
where ∧ denotes the bitwise AND operation. Since the sum could be large, compute it modulo 10^9+7.
EXPLANATION
Let X_i=L∧(L+1)∧...∧i), for i>=L. Here ∧ denotes bitwise AND operation.
If we consider a particular bit, say j^{th} bit, in the binary representation of all X_i. Let the number of terms in which it is 1 be c_j.
Then,
\sum_{i=L}^{i<=R} X_i = \sum_{j=0}^{j<60}c_j*2^j.
How to compute c_j ?
Claim : If we consider any particular bit in the binary representation of Xis, it will be 1 in some number of consecutive terms from the beginning of the sequence , and then 0 in remaining terms of the sequence".
Proof: Let us consider jth bit.
- If it is 1, in all the terms, the claim is true.
- If it becomes 0 in some term, let the first term at which it becomes 0 be X_K. Now, any further term in the sequence X_T can be written as X_T=X_K∧(k+1)...∧T, and since j^{th} bit is 0 in X_K, it is 0 in X_T also. Hence, the claim is true!
The first term in which the j^{th} bit becomes 0 is X_K where K is the smallest integer >=L with j^{th} bit is 0.
- K=L, if j^{th} bit is 0 in L.
-
K=L+(2^j-(L\& (2^j-1))) , if j^{th} bit is 1 in L.
Let’s look at how this comes.
For exapmle, let L=26, in binary form L=“11010” and let’s consider 3rd(0-based) bit i,e 11010 (highlighted bit).
L+1 = 27 = “11011”
L+2 = 28 = “11100”.
L+3 = 29 = “11101”.
L+4 = 30 = “11110”.
L+5 = 31 = “11111”.
L+6 = 32 =“100000”.
We see that , it remains 1 until all bits smaller than j are all 1.
Let P be the number where all bits smaller than j are all 1, then K=P+1.(from the way we defined K).
If we observe, the bits which are >=j i.e, j^{th} bit, j+1^{th} bit,…, they are same in L and P.
Therefore, P and L differ only in first j bits i.e (0^{th} bit, 1^{st} bit, …(j-1)^{th} bit)
Hence, P-L = (value of first j bits in P) - (value of first j bits in L).
Value of first j bits in P : (2^j-1) , because all j bits are 1’s.
Value of first j bits in L : (L\&(2^j-1)), because (2^j-1) in binary representation is simply, “111…11” ( j 1’s ) , (L\&(2^j-1)) gives the value of first j bits of L, because any bit beyond j is 0 in (2^j-1).
Hence,
P-L = (2^j-1) - (L\&(2^j-1)).
=>P=L+(2^j-1) - (L\&(2^j-1)).
and,
K=P+1
=>K=L+(2^j-1) - (L\&(2^j-1))+1.
=>K=L +2^j - (L\&(2^j-1)).
Therefore, c_j=min(K-L,R-L+1).
TIME COMPLEXITY:
Calculating c_j : O(1) per j, Total time : O(log R) for all log R bits.
Calculating \sum_{i=L}^{i<=R} X_i : O(log R).
Total Time complexity : O(log R) per test case.
SOLUTIONS:
Setter's Solution
import java.util.*;
import java.io.*;
class Solution{
final static long mod = (long)1e9+7;
public static void main(String[] args){
FastReader s = new FastReader(System.in);
PrintWriter w = new PrintWriter(System.out);
int t = s.nextInt();
while(t-->0){
long L = s.nextLong(), R = s.nextLong(), ans = 0, cur = L, pow = 1;
for(int i = 0; cur > 0; i++, cur >>= 1, pow <<= 1, pow %= mod) {
if((cur&1) == 0) continue;
long temp = cur + 1; //This operation sets the first unset bit after i
temp <<= i; //Now we need to left shift temp by i, since our current cur is right shifted i times.
ans += pow * ((Math.min(R, temp - 1) - L + 1)%mod);
ans %= mod;
}
w.print(ans + "\n");
}
w.close();
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader(InputStream i) { br = new BufferedReader(new InputStreamReader(i)); }
String next() {
while (st == null || !st.hasMoreElements()) {
try{
st = new StringTokenizer(br.readLine());
}
catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() { return Integer.parseInt(next()); }
long nextLong() { return Long.parseLong(next()); }
}
}
Tester's Solution
#include <bits/stdc++.h>
#define endl '\n'
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back
using namespace std;
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
const int mod = (int)1e9 + 7;
int64_t L, R;
void read() {
cin >> L >> R;
}
void solve() {
int64_t answer = 0, mask = 0;
for(int64_t i = 1; i <= R; i <<= 1ll) {
if(L & i) {
int64_t mult_by = i - (L & mask);
chkmin(mult_by, R - L + 1);
mult_by %= mod;
answer = (answer + (i % mod) * 1ll * mult_by) % mod;
}
mask |= i;
}
cout << answer << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin >> T;
while(T--) {
read();
solve();
}
return 0;
}
Editorialist's Solution
//raja1999
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
//std::ios::sync_with_stdio(false);
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t,t1;
cin>>t;
t1=t;
while(t--){
int l,r,act=0,req=0,val,ans=0,i;
cin>>l>>r;
for(i=0;i<60;i++){
val=min(r-l+1,req-act+1);
val%=mod;
if(l&(1LL<<i)){
ans+=(val*((1LL<<i)%mod))%mod;
ans%=mod;
act+=(1LL<<i);
}
req+=(1LL<<i);
}
cout<<ans<<endl;
}
return 0;
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 
