### PROBLEM LINK:

**Author:** Misha Chorniy

**Tester:** Karan Aggarwal

**Editorialist:** Pushkar Mishra

### DIFFICULTY:

Easy

### PREREQUISITES:

None

### PROBLEM:

Given a number N, find the number of integers X such that X + S(X) + S(S(X)) = N. Here, S(k) denotes sum of digits of integer K.

### EXPLANATION:

The first thing to note is that no number strictly greater than N can satisfy the equation. So we only care about numbers less than or equal to N.

The next thing to note is that we are given the constraint that N \leq 10^9. This means S(X) can at maximum be 81 for any X \leq N. This is because the largest number below 10^9 is 999999999 whose digits add up to 81. The digits of 10^9 add up to 1 anyway. So, S(X) \leq 81, and we have that S(S(X)) \leq 16 (maximum case is for 79). Summing the two inequalities, we have that S(X) + S(S(X)) \leq 97.

This gives us an efficient algorithm to calculate the number of integers that satisfy the equation. Since, S(X) + S(S(X)) \leq 97, we just need to iterate from X = N-97 to N and check which integers satisfy the equation because no integer smaller than N-97 can satisfy the equation and neither can any integer greater than N.

Please see editorialist’s/setter’s program for implementation details.

### COMPLEXITY:

\mathcal{O}(97)