This question already has an answer here:
- smallest number for given sum of digits 3 answers
let us suppose that we have a number x and we need to find the smallest number larger than x who sum of digits are y. As an example lets take 3 as x and we need to find a number larger than x for which sum of digits is 2 and the answer is 11 . what should be the strategy ? I GOT this while solving a problem .can i get an example of how to solve this ? iterate through the digits of y from right to left, trying to increase the current digit and somehow change the digits to the right in order to reach the sum of digits equal to x. Note that if we are considering the (k + 1)-th digit from the right and increase it, we can make the sum of k least significant digits to be any number between 0 and 9k. When we find such position, that increasing a digit in it and changing the least significant digits gives us a number with sum of digits x, we stop the process and obtain the answer. Note that if k least significant digits should have sum m (where 0 ≤ m ≤ 9k), we should obtain the answer greedily, going from the right to the left and putting to the position the largest digit we can.