FindMaxLessSum (Editorial)

Approach

To maximize $v$, we need to stay as close to $n$ as possible while reducing the digit sum. The most efficient way is:

1. Traverse the digits of $n$ from right to left (least significant to most significant).

2. Find the first non-zero digit.

3. Decrease that digit by $1$.

Example

• If n = 1230, the rightmost non-zero digit is $3$.

• Decrease it by 1 \to v = 1220.

• S(1230) = 6, while S(1220) = 5.

Why does this work?

• Minimal Reduction: By changing the rightmost non-zero digit, we are subtracting the smallest possible value (the smallest power of $10$) that actually reduces the digit sum.

• Maximality: Any number $x$ such that v < x < n would have to keep all digits to the left of our changed position the same. Since the digits to the right of our changed position in $n$ were all $0$, any $x$ in that range would require at least one of those $0$s to become a larger digit, which would make S(x) \ge S(n).

• Sum Change: This operation always results in S(v) = S(n) - 1, which is the closest possible sum to the original.

• Time Complexity: O(\log(\max N))

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n ;
    cin >> n ;
    vector <int> a ;
    while(n) {
      a.push_back(n % 10) ;
      n /= 10 ;
    }
    int k = (int) a.size() ;
    for(int i = 0 ; i < k ; i ++) {
      if(a[i]) {
        a[i] -- ;
        break ;
      }
    }
    int ans = 0 ;
    int p = 1 ;
    for(int i = 0 ; i < k ; i ++) {
      ans += a[i] * p ;
      p *= 10 ;
    }
    cout << ans << endl ;
    
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // freopen("output.txt", "w", stdout);
    // freopen("input.txt", "r", stdin);
    int t ;
    cin >> t ;
    while(t --) {
        solve() ;
    }
    return 0;
}