# TED24 - EDITORIAL

Contest
Practice
Author: Chirantan Muliya
Tester: Tushar Sain
Editorialist: Chirantan Muliya

MEDIUM

### PREREQUISITES

Binary numbering system, Bit manipulation, PnC

### EXPLANATION & SOLUTION:

Take log_2(10^3)=10,log_2(10^9)=30,log_2(10^{18})=60.

Brute force approach check for all numbers between a to b if number of 0 bits are 3 or not…

#### Space complexity: O(1)

Count number of bits in A and B, Check all possible combinations with 3 zeroes for bits_a and bits_b and increase count for those numbers which are in range [A,B].

#### Space complexity: O(1)

Hint: Precomputation for all bits (0…61) in Subtask2 will remove T factor.

#### Space complexity: O(10^5)

Setter's Solution :
``````#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define loopf(i, a, b) for (ll i = a; i < b; i++)
#define loopb(i, a, b) for (ll i = a; i > b; i--)
#define pb push_back
#define fast                          \
ios_base::sync_with_stdio(false); \
cin.tie(NULL);
#define ff first
#define ss second
#define vc vector
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mapii map<int, int>
#define mapll map<ll, ll>
#define all(x) x.begin(), x.end()
#define endl "\n"
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
for (auto &i : a) \
cin >> i
#define print(a)     \
for (auto i : a) \
cout << i << " "
#define ub(v, i) upper_bound(all(v), i)
#define lb(v, i) lower_bound(all(v), i)
const ll M = 1e9 + 7;
const ll N = 100001;
vc<ll> v, pow2;
void solve()
{
ll l, r;
cin >> l >> r;
cout << ub(v, r) - lb(v, l) << endl;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
fast
int t = 0;
cin >> t;
pow2.resize(65); // for safe side taking 65.. we can take 61 also
pow2[0] = 1;
ll xx = 2;
loopf(i, 1, 65) pow2[i] = xx, xx <<= 1; // generating 2^i
loopf(i, 3, 64)
{
ll curr = pow2[i + 1] - 1; // generating 2^(i+1)-1 which will be 111...1 i+1 times
loopf(j, 0, i) loopf(k, 0, j) loopf(l, 0, k) // taking all possible combinations for three 0 bits except for MSB
v.pb(curr - pow2[j] - pow2[k] - pow2[l]);
// subtracting pow2[j] will make jth bit 0 and so on
// e.g. for curr=1111, we will subtract 0100 0010 0001 which will give us 1000
}
sort(all(v));
int c = 1;
while (c <= t)
{
solve(), c++;
}
}

``````

#### Please comment below for any doubts or if you have alternative solution(s)

Here is my solution without precomputing using simple combinatorics:)
(I realised i did a very small looking huge mistake in my code XD so i had to delete my previous post )

To be honest , i really liked your solution of precomputing , when i first saw this problem the same idea came to my mind , but i didn’t realised that the numbers will not be many and we can do precomputation . Thanks a lot , learnt something new today

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

#define all(v) v.begin(),v.end()
#define vi vector <int>
#define sim template<typename T

sim > istream &operator>>(istream &is , vector<T> &container){
for(auto &item : container ){
is >> item;
}
return is;
}

sim > ostream &operator<<(ostream &os , vector<T> &container){
auto itr = container.begin();

for(auto item : container){
os << item;
if(++itr != container.end()) os << ' ';
}
return os;
}

int combo(int n , int r){
if(min({n , r , n - r}) < 0) return 0;
if(r == 0) return 1;

if(r == 1){
return n;
}
if(r == 2){
return (n * (n - 1))/2;
}

if(r == 3) return (n * (n - 1) * (n - 2))/6;
}

void SOLVE(){

auto binary = [](int x) -> string{
string res = "";
for( ; x > 0; x >>= 1) res.push_back(x % 2 + '0');
reverse(all(res));
return res;
};

auto isIt = [&binary](int x) -> int{
int count = log2(x) - __builtin_popcount(x) ;
return count == 3;
};

auto right = [&binary](int L) -> int{
string l = binary(L);
int d = l.size();
int req = 3;
int ans = ((d - __builtin_popcount(L)) == req);

for(int i = 0; i < d; i++){
if(l[i] == '1') continue;
ans += combo(d - i - 1 , req);
req--;
}
return ans;

};

auto left = [&binary](int R) -> int{
string r = binary(R);
int d = r.size();
int req = 3;
int ans = ((d - __builtin_popcount(R)) == req);

for(int i = 1; i < d; i++){
if(r[i] == '0'){
req--;
continue;
}
ans += combo(d - i - 1 , req - 1);
}

return ans;
};

int L , R; cin >> L >> R;
string l = binary(L) , r = binary(R);

int ans = 0;

if(l.size() == r.size()){

int digits = l.size();

ans = combo(digits - 1 , 3);

if(L - 1 >= 1ll << (digits - 1)) ans -= left(L - 1);

if(R + 1 <= (1ll << digits) - 1) ans -= right(R + 1);
}

else{

ans = right(L) + left(R);
for(int i = l.size() + 1; i <= r.size() - 1; i++){
ans += combo(i - 1 , 3);
}
}

cout << ans << "\n";

}

int32_t main(){

cin.tie(0)->sync_with_stdio(0);
int t = 1;cin >> t;
while(t--){
SOLVE();
}

}

``````

Though for larger number of zeroes , we couldn’t possibly write multiples loops for precomputing and the numbers can increase too , so we then have to calculate the answer using combinatorics with respect to some mod

@sain2801 Bro , actually i am not able to submit my code for practice tab it is showing me some error , can u please confirm when will the problem be available for practice . Though i am getting correct outputs in stress testing , but still it would be great if i can confirm whether it is fully correct or not.

where can i submit the solution after the contest has ended ? it says access denied

Hey!! @prakhar_jn check now you can submit it in practice link here

Hey @letsdosmtgdiff I looked your code I think it is correct only though you can check once submitting here. You did a great observation there!! Thank you for letting me know another approach.

1 Like

Thanks bro, i checked and it got accepted(Solution: 56271109 | CodeChef)