SRM 699, D2, 500-Pointer (LastDigit)

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> g++ badloop.cpp
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 <string>
#include <map>
#include <iostream>
#include <cstdio>
#include <cstdlib>
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;
}