Get n-th perfect number

Question

The task:

A number is considered perfect if its digits sum up to exactly 10.

Given a positive integer n, return the n-th perfect number.

For example, given 1, you should return 19. Given 2, you should return 28.

My solution:

const sum = (acc, m) => acc + Number(m);
const getNthPerfectNumber = n => {
  let i = 0, x = 0;
  while (i !== n) {
    x++;
    if (x
      .toString()
      .split('')
      .reduce(sum, 0) === 10) { i++; }
  }
  return x;
};

console.log(getNthPerfectNumber(2));

Answer 1

Computers do numbers!

Compared to manipulating numbers, strings are very slow and use a lot of memory relative to what is being done.

To test if it is a perfect integer

const isPerfectInt = num => {
    var sum = (num | 0) % 10;
    while (num > 0) { sum += (num = num / 10 | 0) % 10 }
    return sum === 10;
}

Improved cache

You are caching results in your answer and you only cache what you are looking for. However while you are searching you find all the perfect values below the one you are looking for. This negates most the advantage you get from caching calculations.

If you keep all calculated perfect numbers you can then use that last calculated value as a starting point. That way you will never test the same value twice.

const cache = [0,19];  // set up first value. Saves some messing about
const getNthPerfectNumber = n => {
    if (cache[n]) { return cache[n] }

    // Start from the last number tested plus one.
    var idx = cache.length - 1, num = cache[idx] + 1;
    while (idx < n) {
        if (isPerfectInt(num)) { cache[++idx] = num }
        num++;
    }
    return num - 1;
};

Answer 2

There's not a lot of code to review here, but what I would say is that the sum function is probably the wrong function to extract. It would make the entire thing more readable if you instead extracted a digitSum function.

Answer 3

I'd say one small optimization you could do is start x at 18, since none of the numbers below 19 would have digits that add up to 10. That way there would be quite a few less operations/function calls - this is important to be aware of with functional programming.

Also, if the function gets run multiple times, then it would be beneficial to memorize it- specifically, store results of calls to compute the digit sums for various values (of x) so they can be looked up quicker than re-computing them.

Answer 4

    x++;

This is very inefficient.

The intended approach is probably to write a successor function which takes a "perfect"¹ number and gives the next one by manipulating its digits. The optimal approach probably starts by getting a fast calculation for the number of "perfect" numbers with \$d\$ digits.

But even if you want to use brute force, there's an easy speed-up by a factor of 10:

let i = 0, prefix = 0;
while (i < n) {
    prefix++;
    lastDigit = 10 - digitSum(prefix);
    if (lastDigit >= 0 && lastDigit <= 9) i++;
}

---

¹ The term "perfect number" already means something else, and they should have chosen a different name.

Answer 5

After suggestion by @Magnus Jeffs Tovslid and @Sᴀᴍ Onᴇᴌᴀ:

const memoizedPerfectNumbers = [];
const sum = (acc, m) => acc + Number(m);
const digitSum = x => x
      .toString()
      .split('')
      .reduce(sum, 0);
const getNthPerfectNumber = n => {
  if (memoizedPerfectNumbers[n - 1]) { return memoizedPerfectNumbers[n - 1]; }
  let i = 0, x = 18;
  while (i !== n) {
    x++;
    if (digitSum(x) === 10) { i++; }
  }
  memoizedPerfectNumbers[n - 1] = x;
  return x;
};
console.log(getNthPerfectNumber(2));
console.log(memoizedPerfectNumbers);
console.log(getNthPerfectNumber(2));