Double or Double Plus One
National Olympiad — National round (2023 season)
Submission name: Mul2Add1.cpp
Problem summary
Start at zero. Operation 1 doubles the current number; operation 2 doubles it and adds one. Find a shortest sequence reaching N.
Input
One integer N.
Output
The minimum operation count, then the sequence of operation numbers 1 or 2.
Constraints
1 ≤ N ≤ 10^9.
Worked example
An independently prepared example for this explanation.
Input
5
Output
3 2 1 2
Solution analysis
- Doubling shifts a binary number left by one bit. Adding one after doubling appends a one instead of a zero. Thus the operations write the binary digits of N from left to right.
- Extract bits from right to left with remainder modulo two, reverse them, and output operation 1 for bit zero and operation 2 for bit one.
- For N=5, binary 101 gives operations 2,1,2: 0→1→2→5. A leading zero would waste an operation, so begin at the highest one bit.
Why it works
After k operations the number is less than 2^k, so a number with L binary digits needs at least L operations. Appending its L binary digits constructs it in exactly L operations, proving minimality.
Complexity: O(log N) time and O(log N) extra space.
Watch out. Operation labels are 1 for a zero bit and 2 for a one bit. Reverse the extracted bits before printing.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> operations;
while (n > 0) {
operations.push_back(n % 2 + 1);
n /= 2;
}
// Extracted low bits must be reversed to build N from its leading bit.
reverse(operations.begin(), operations.end());
cout << operations.size() << '\n';
for (int i = 0; i < static_cast<int>(operations.size()); i++) {
if (i > 0) {
cout << ' ';
}
cout << operations[i];
}
cout << '\n';
}