Friendly Numbers

Research check: the official Codeforces editorial for Round 1079 uses the same bounded brute force idea, checking only a small window after $x$ (official editorial). A public explanation also phrases it as trying possible digit sums $1\ldots 90$ and links a submitted solution (write-up). The supplied statement is still the source of truth.

We need count integers $y$ such that

$$y-d(y)=x,$$

where $d(y)$ is the sum of digits of $y$.

Rearrange it:

$$y=x+d(y).$$

That is the whole problem. A friendly number $y$ cannot be far from $x$; the only extra amount is its digit sum.

Now bound that digit sum. Suppose $y$ has $k$ digits. Then

$$d(y)\le 9k.$$

If $k\ge 11$, then

$$y-d(y)\ge 10^{k-1}-9k \ge 10^{10}-99 > 10^9,$$

which is impossible because the statement guarantees $x\le 10^9$. So every valid $y$ has at most $10$ digits, meaning

$$d(y)\le 90.$$

Therefore every valid friendly number has the form

$$y=x+s$$

for some integer $s$ with $1\le s\le 90$, where $s$ is supposed to equal $d(y)$.

So we just try every possible $s$:

1. Set $y=x+s$.
2. Compute $d(y)$.
3. If $d(y)=s$, count it.

Why this is correct:

Every valid friendly number $y$ has exactly one digit sum $s=d(y)$. From $y-d(y)=x$, it must satisfy $y=x+s$, so our loop checks that exact candidate. If the candidate passes $d(x+s)=s$, then

$$(x+s)-d(x+s)=(x+s)-s=x,$$

so it is definitely friendly. If it fails, that guessed digit sum was nonsense. Brutal, but fair.

There is no double-counting because each $s$ produces only one candidate $y=x+s$, and every integer has exactly one digit sum.

Edge cases:

• $x=1$: candidates $2,3,\ldots,91$ are checked, none satisfy the equation, so the answer is $0$.
• Values near $10^9$: use long long, because $x+s$ is still small, but 64-bit integers keep the code clean and avoid dumb overflow worries.
• $s=0$ is impossible for positive $y$, so we start from $1$.

Complexity per test case is

$$O(90\cdot \text{digits})=O(1),$$

with $O(1)$ memory. With $t\le 500$, this is basically instant.