Codingame Solution: Digit sum successor

Solution

The idea is to increment the last digit that is not a nine by one to make it larger than the given number. To maintain the sum of the digits, we decrement a non-null digit on a less significant position. Because none of the digits after the incremented digit are relevant to make the resulting number larger than the original number, we sort the less significant digits to minimize the value of the result.

To handle an array underflow correctly, we push a zero element in front of the array of digits, which gets removed at the end by turning the array into a number. The resulting algorithm can be implemented in Ruby like this

a = [0] + gets.split('').map(&:to_i)

# Index of last non-zero digit
n = a.rindex { |e| e > 0 }

# Index of last non-nine digit before n
m = a[0..n-1].rindex { |e| e < 9 }

# Balance digit sum
a[m]+= 1
a[n]-= 1

# Sort the less-significant digits of the number to minimize it
a[m + 1..-1] = a[m + 1..-1].sort

puts a.join.to_i