Binary Zeros
National Olympiad — Regional round (2018 season)
Submission name: bin0.cpp
Problem summary
Count positive integers in the inclusive interval [s,t] whose ordinary binary representation has exactly z zero digits. Leading zeros are not part of the representation.
Input
s t z.
Output
The count.
Constraints
1 ≤ s ≤ t ≤ 10^18; 0 ≤ z ≤ 60.
Worked example
Official sample, transcribed with whitespace restored from the PDF.
Input
8 23 2
Output
6
Solution analysis
- Compute F(t)−F(s−1), where F(x) counts eligible positive integers at most x. Precompute binomial coefficients C[n][k] for n≤60. Among all numbers of binary length L, the leading bit is fixed to one, and the remaining L−1 positions contain z zeros in C[L−1][z] ways.
- For numbers with the same length as x, scan its bits after the leading one. Whenever the current bit of x is one, create the smaller branch by writing zero here; choose the remaining zeros freely among all lower positions. Then continue along the branch equal to x. A zero in x consumes one required zero. Finally include x itself if its zero count is z.
- For [8,23] and z=2, the length-four matches are 1001, 1010, and 1100. The length-five matches within the interval are 10011, 10101, and 10110. Their total is six.
Why it works
Every positive integer has a unique binary length. Shorter lengths are counted by choosing their zero positions. At the same length, each number smaller than x has a unique first differing bit, where x has one and it has zero; the scan counts exactly that branch. The final equality check adds x once, proving F and the interval difference correct.
Watch out. Do not count zero or padded leading zeros. Invalid binomial arguments contribute zero. Use 64-bit counts.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
long long chooseCount[61][61];
long long combination(int n,int k){
return k<0||k>n?0:chooseCount[n][k];
}
long long countUpTo(long long x,int zeros){
if(x<=0){
return 0;
}
string bits;
for(long long value=x;value;value/=2){
bits.push_back(char('0'+value%2));
}
reverse(bits.begin(),bits.end());
int length=int(bits.size());
long long answer=0;
for(int size=1;size<length;++size){
answer+=combination(size-1,zeros);
}
int used=0;
for(int i=1;i<length;++i){
if(bits[i]=='1'){
// First difference: this bit is zero, all later bits are free.
answer+=combination(length-i-1,zeros-used-1);
}
else{
++used;
}
}
return answer+(used==zeros);
}
int main(){
for(int n=0;n<=60;++n){
chooseCount[n][0]=chooseCount[n][n]=1;
for(int k=1;k<n;++k){
chooseCount[n][k]=chooseCount[n-1][k-1]+chooseCount[n-1][k];
}
}
long long s,t;
int z;
cin>>s>>t>>z;
cout<<countUpTo(t,z)-countUpTo(s-1,z)<<'\n';
}