### James S. Plank

Wed Nov 23 14:59:12 EST 2016
For inspiration, take a look at an example where S is 1370. The answer is 1234: (1234 + 123 + 12 + 1) = 1370. Now, let's reorder that sum so that it helps us solve the problem. Instead of (1234 + 123 + 12 +1), we can view the sum as:

1111 + 222 + 33 + 4

That helps us spot the recursion for a dynamic programming solution. Find the number T, which is the largest number less than or equal to S which is composed of the same digit repeated. In the example above, T is 1111. And then find the number I, which is the first digit of T, followed by all zeros. In the example above, I is 1000.

Solve the problem recursively on (S-T), and add I to the solution. In the example above, you solve the problem on 259, whose answer is 234, and add 1000, so that the answer to 1370 is 1234. Put in a base case, memoize, and you're done. Or are you? Are there things that can go wrong?

Let's think of a few. First, what happens when S is less than 1111? In that case, you'll have to set T to 999, so you'll need to be ready for that case. That will help with some problems -- for example, when S is 1001, then we'll set T to 999, and sove the subproblem with S equals 2. The answer will be 902. That works.

However, it doesn't always work. Suppose S is 1110. Then T is 999, and you'll solve the problem recursively on (1110-999) = 111. That answer is 100, but you can't add it to 900 -- both the answer and T are three digits. You'll need to account for that problem.

Finally, the constraints present another challenge. S can be as big as (1018), which means that you need to be careful calculating T. When I first tried to solve this problem, I got tripped up on this issue. My loop was the following:

```  T = 0;
while (T <= S) T = 10*T + d;
```
When S was 999,999,999,999,999,999 (example 5), the loop above calculates the wrong value of T, because 10(999,999,999,999,999,999) overflows. I'll illustrate:
```UNIX> cat badloop.cpp
#include
#include
using namespace std;

int main()
{
long long S, T;
int d;

S = 999999999999999999LL;
T = 0;
while (T <= S) {
T = T*10 + 9;
printf("%lld\n", T);
}
return 0;
}
UNIX> a.out
9
99
999
9999
99999
999999
9999999
99999999
999999999
9999999999
99999999999
999999999999
9999999999999
99999999999999
999999999999999
9999999999999999
99999999999999999
999999999999999999
-8446744073709551617
7766279631452241919
UNIX>
```
So, instead of using numbers to calculate T and I, I used strings. I also converted the return value of the recursive call to a string, so that I could make sure that it had fewer digits than T.

Finally, you actually don't have to memoize this program, because there is no exponential blowup of recursive calls -- each call to findX() makes at most one recursive call, to a value that is roughly a factor of 10 smaller. No memoization necessary!

The solution is in Solution.cpp.

 ```/* Topcoder SRM 699, D2, 500-pointer: LastDigit. * James S. Plank * Fri Nov 25 11:20:03 EST 2016 */ #include #include #include #include #include using namespace std; class LastDigit { public: long long findX(long long S); }; long long LastDigit::findX(long long S) { long long T; /* T is the biggest number <= S with all repeated digits. */ long long I; /* I is the first digit of T with all zeros. */ long long RV; /* This is the return value of the recursive call */ string SS; /* The string version of S. */ string ST; /* The string version of T. */ string SI; /* The string version of I. */ string SRV; /* The string version of RV. */ char buf[50]; /* This is to convert long long's to strings. */ int i; /* Base case. */ if (S < 10) return S; /* Create string version of S. */ sprintf(buf, "%lld", S); SS = buf; /* Create ST from SS. If it's too big, then either subtract all 1's from it, or make it be all 9's, and one digit smaller. */ ST = buf; for (i = 1; i < ST.size(); i++) ST[i] = ST[0]; if (ST > SS) { if (ST[0] != '1') { for (i = 0; i < ST.size(); i++) ST[i]--; } else { for (i = 0; i < ST.size(); i++) ST[i] = '9'; ST.pop_back(); } } /* Now, create SI, and convert SI and ST back to I and T */ SI = ST; for (i = 1; i < SI.size(); i++) SI[i] = '0'; sscanf(ST.c_str(), "%lld", &T); sscanf(SI.c_str(), "%lld", &I); /* Make the recursive call, and check to make sure that the return value is not too big. */ RV = findX(S-T); if (RV != -1) { sprintf(buf, "%lld", RV); SRV = buf; if (SRV.size() == ST.size()) RV = -1; } /* If the return value is ok, then add I, and you're done. */ if (RV != -1) RV += I; return RV; } ```