Longest Run of Digital Roots
National Olympiad — National round (2024 season)
Submission name: sequence.cpp
Problem summary
Repeatedly replace every positive array value by its digit sum until it becomes a single digit. In the transformed array, find the first longest contiguous nondecreasing subsequence.
Input
N, then N positive integers.
Output
The chosen subsequence length, then its transformed elements in order.
Constraints
2 ≤ N ≤ 100000; input numbers have at most 10 decimal digits.
Worked example
An independently prepared example for this explanation.
Input
5 7 11 14 9 15
Output
3 2 5 9
Solution analysis
- Compute each number’s final digit using repeated digit summation. Store the resulting one-digit array, which is the array from which the answer must be printed.
- Scan it while tracking the start of the current nondecreasing run. A strict decrease starts a new run. Update the best start and length only when the new run is strictly longer, preserving the earliest answer on ties.
- The sample transforms 7,11,14,9,15 into 7,2,5,9,6. The longest run is 2,5,9, of length three; original values 11 and 14 must not be printed.
Why it works
Repeated digit sums implement exactly the prescribed transformation and terminate at one digit. Every maximal nondecreasing run starts at the beginning or after a strict decrease; the scan examines all their prefixes and thus their full lengths. Strict improvements preserve the first optimum.
Watch out. Use long long to read ten-digit values. Equal neighboring roots extend a run. Resolve ties by keeping the earlier start.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
using namespace std;
int digitalRoot(long long value) {
while (value >= 10) {
long long sum = 0;
while (value > 0) {
sum += value % 10;
value /= 10;
}
value = sum;
}
return static_cast<int>(value);
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int &value : a) {
long long original;
cin >> original;
value = digitalRoot(original);
}
int start = 0, bestStart = 0, bestLength = 1;
for (int i = 0; i < n; i++) {
if (i > 0 && a[i] < a[i - 1]) {
start = i;
}
int length = i - start + 1;
// Strict improvement keeps the earliest run when lengths tie.
if (length > bestLength) {
bestLength = length;
bestStart = start;
}
}
cout << bestLength << '\n';
for (int i = 0; i < bestLength; i++) {
if (i > 0) {
cout << ' ';
}
cout << a[bestStart + i];
}
cout << '\n';
}