find kth good number

Let's start with a simple question:

1. I give you a list of five consecutive numbers. How many of those numbers are divisible by 5? (I'm not talking abouts sums of digits yet. Just the numbers, like 18, 19, 20, 21, 22.

No problem there, right? So a slightly different question:

2. In a list of ten consecutive numbers, how many are divisible by 5?

Still pretty easy, no? Now let's look at your "good" numbers. We'll start by introducing the function digit_sum(n), which is the sum of the digits in n. For now, we don't need to write that function; we just need to know it exists. And here's another simple question:

3. If n is a number which does not end in the digit 9 and s is digit_sum(n), what is digit_sum(n+1)? (Try a few numbers if that's not immediately clear.) (Bonus question: why does it matter whether the last digit is 9? Or to put it another way, why doesn't it matter which digit other than 9 is at the end? What's special about 9?)

Ok, almost there. Let's put these two ideas together:

4. Suppose n ends with 0. How many of the ten numbers digit_sum(n), digit_sum(n+1), digit_sum(n+2), … digit_sum(n+9) are divisible by 5? (See question 2).

Does that help you find a quick way to compute the kth good number after n? Hopefully, the answer is yes. Now you just need to generalise a little bit.

maybe your digits algorithm is too time consuming? try this:

def digits(n):
  sum = 0
  while n:
    n, r = divmod(n, 10)
    sum += r
  return sum
  
def solve(n,k):
  n+=1
  count = 0
  while count<k:
    if digits(n)%5==0:
      count+=1
    n+=1
  return n-1

still it’s a trivial solution, and always you can run it offline and just submit a lookups table.

And here is a link for this sequence: http://oeis.org/A227793

Here's a digit dynamic-program that can answer how many such numbers we can find from 1 to the parameter, k. The function uses O(num_digits) search space. We could use it to search for the kth good number with binary search.

The idea generally is that the number of good numbers that include digit d in the ith position, and have a prefix mod 5 of mod1 so far, is equal to the count of valid digit-suffixes that have the complementary mod, mod2, so that (mod1 + mod2) mod 5 = 0.

JavaScript code comparing with brute force:

function getDigits(k){
  const result = [];
  while (k){
    result.push(k % 10);
    k = ~~(k / 10);
  }
  return result.reverse();
}

function g(i, mod, isK, ds, memo){
  const key = String([i, mod, isK]);
  
  if (memo.hasOwnProperty(key))
    return memo[key];
    
  let result = 0;
  const max = isK ? ds[i] : 9;
    
  // Single digit
  if (i == ds.length-1){
    for (let j=0; j<=max; j++)
      result += (j % 5 == mod);
    return memo[key] = result;
  }
  
  // Otherwise
  for (let j=0; j<=max; j++){
    const m = j % 5;
    const t = (5 + mod - m) % 5;
    const next = g(i+1, t, isK && j == max, ds, memo);
    result += next;
  }
  
  return memo[key] = result;
}

function f(k){
  if (k < 10)
    return (k > 4) & 1;
  
  const ds = getDigits(k);
  const memo = {};
  let result = -1;
  
  for (let i=0; i<=ds[0]; i++){
    const m = i % 5;
    const t = (5 - m) % 5;
    const next = g(1, t, i==ds[0], ds, memo);
    result += next;
  }
  
  return result;
}

function bruteForce(k){
  let result = 0;
  //let ns = [];
  
  for (let i=1; i<=k; i++){
    const ds = getDigits(i);
    const sum = ds.reduce((a, b) => a + b, 0);
    if (!(sum % 5)){
      //ns.push(i);
      result += 1;
    }
  }
  //console.log(ns);
  return result;
}

var k = 3000;

for (let i=1; i<k; i++){
  const _bruteForce = bruteForce(i);
  const _f = f(i);
  if (_bruteForce != _f){
    console.log(i);
    console.log(_bruteForce);
    console.log(_f);
    break;
  }
}

console.log('Done.');