This page is still under construction.

Parts of this page are still being built. What you see may change.

Digit Sum

Interview

Time limit1sMemory limit512 MB

Summary
Given an integer N up to 10^20, find the smallest integer greater than N whose digits sum to the same value as N's digits.
Level

Medium7 of 10

Topics
Greedy, Math, Implementation, String
Solved
No attempts yet

Problem

Given an integer NN, find the smallest number greater than NN that has the same digit sum as NN.

The digit sum of an integer is the sum of its digits. For example, 9550 has digit sum 9+5+5+0=199 + 5 + 5 + 0 = 19, and 999 has digit sum 9+9+9=279 + 9 + 9 = 27.

Input

An integer, NN.

Output

Print the smallest number greater than NN that has the same digit sum as NN.

Constraints

  • 1≤N<10201 \le N < 10^{20}

Examples4

  1. Example 1

    Input
    8
    Expected output
    17

  2. Example 2

    Input
    92
    Expected output
    119

  3. Example 3

    Input
    200
    Expected output
    1001

  4. Example 4

    Input
    9550
    Expected output
    9604