4
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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$.

$\endgroup$
  • 2
    $\begingroup$ damn...this is so elegant. $\endgroup$ – Marius Jun 7 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.