Finding Round Integer

An integer is round if it is greater than $$0$$ and the sum of its digits in decimal representation is a multiple of $$10$$. Find an optimal procedure to compute the $$N^\text{th}$$ smallest round integer.

E.g. If $$N = 2$$
then Answer is $$28$$
As the first round integer is $$19 (1+9 = 10)$$ and the second round integer is $$28(2+8 = 10)$$

______
Source: https://www.codechef.com/JUNE19B/problems/KS2

The $$N$$th round integer is given by

$$f(N) = 10N + k$$ where $$k$$ is a single digit and $$k \equiv -S(N) \mod 10$$ and $$S(N)$$ is the sum of the digits of $$N$$.

Proof

Take any set of digits $$S$$ and suppose the sum of the digits in $$S$$ is congruent to $$s$$ mod $$10$$. There is exactly one digit $$x$$ which we could add to $$S$$ to make the overall sum divisible by $$10$$, that is, essentially, $$-s$$ mod $$10$$.
This means that for any integer $$N$$, there is exactly one digit that we could append to $$N$$ to make the overall sum of its digits divisible by $$10$$. Hence, for each $$N$$, there exists one digit $$n$$ such that the sum of the digits $$10N + n$$ is divisible by $$10$$. This $$n$$ must be $$-S(N) \mod 10$$

Example

Consider finding the $$2019$$th round number. $$S(2019) = 2 + 0 + 1 + 9 \equiv 2 \mod 10$$ $$\Rightarrow k \equiv -2 \mod 10 \Rightarrow k=8$$ Hence the $$2019$$th round number is $$20198$$.

• damn...this is so elegant. – Marius Jun 7 at 12:50