Counting Runs of Binary Ones
National Olympiad — National round (2022 season)
Submission name: sumpow.cpp
Problem summary
Count positive values≤n equal to a sum of consecutive powers of two, including single powers.
Input
One integer n.
Output
The representable-value count.
Constraints
1≤n≤10^18.
Worked example
Input and output for the worked example discussed below.
Input
10
Output
7
Solution analysis
- Each valid value has one nonempty consecutive run of binary ones. Its lowest and highest set bits uniquely determine the power interval.
- Enumerate the lowest power, repeatedly adding the next doubled power while the sum remains≤n. Each extension counts one value; test limits before additions and doubling.
- For n=10, values1,2,3,4,6,7,8 qualify. Values5,9,10 have separated one-runs, so the answer is7.
Why it works
Every enumerated value is a consecutive-power sum, and every such sum has exactly one lowest/highest-bit pair visited by the loops.
Complexity: O(log²n) time and O(1) space, at most60 starts and60 extensions each.
Watch out. Single terms count. Arbitrary power subsets would represent all integers; consecutiveness is essential. Avoid doubling overflow.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
using namespace std;
// Every enumerated value is a consecutive-power sum, and every such sum has exactly one lowest/highest-bit
// pair visited by the loops.
int main(){
long long limit;
cin>>limit;
long long answer=0;
for(long long first=1;first<=limit;){
long long total=0,term=first;
while(term<=limit-total){
total+=term;
answer++;
if(term>limit/2){
break;
}
term*=2;
}
if(first>limit/2){
break;
}
first*=2;
}
cout<<answer<<'\n';
}