Recover the Number of Concatenated Powers
National Olympiad — Regional round (2017 season)
Submission name: degrees.cpp
Problem summary
A valid string concatenates2^1,2^2,…,2^n without separators. Recover n.
Input
The concatenated decimal string.
Output
The exponent count n.
Constraints
Input length1…160000; the string is guaranteed to have the described form.
Worked example
Input and output for the worked example discussed below.
Input
2481632
Output
5
Solution analysis
- Every additional power adds at least one written digit. Consequently cumulative written length increases strictly, so the valid input length uniquely identifies n.
- Generate exact powers by repeatedly doubling a decimal string, starting at1. After each doubling increment the exponent count and add that power’s string length to the cumulative total. Stop at the input length.
- The string2481632 contains2,4,8,16,32, whose lengths1,1,1,2,2 sum to7. Five doublings therefore identify n=5. Exact carries avoid logarithm rounding near powers of ten.
Why it works
After t iterations the stored string equals2^t and the cumulative total equals the lengths of2^1…2^t. Strict increase and the valid-input promise give a unique matching t.
Complexity: O(S) time and O(S) space for input length S. The lengths scanned by all doublings sum to S.
Watch out. Begin at2^1 rather than2^0. This method uses the valid-input promise; it is not an independent verifier of arbitrary strings.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
using namespace std;
int main(){
string input;
cin>>input;
string power="1";
size_t written=0;
int count=0;
while(written<input.size()){
int carry=0;
for(int i=int(power.size())-1;i>=0;i--){
int value=2*(power[i]-'0')+carry;
power[i]=char('0'+value%10);
carry=value/10;
}
if(carry!=0){
power.insert(power.begin(),char('0'+carry));
}
count++;
// Cumulative lengths strictly increase for the promised concatenation.
written+=power.size();
}
cout<<count<<'\n';
}