5
\$\begingroup\$

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));
\$\endgroup\$
  • 1
    \$\begingroup\$ I rolled back your last edit. After getting an answer you are not allowed to change your code anymore. This is to ensure that answers do not get invalidated and have to hit a moving target. If you have changed your code you can either post it as an answer (if it would constitute a code review) or ask a new question with your changed code (linking back to this one as reference). Refer to this post for more information \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Feb 13 at 21:32
3
\$\begingroup\$

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;
};
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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));
\$\endgroup\$
  • \$\begingroup\$ I should have worded my answer. I was trying to point out that calls to compute the digit sums of values (like x in your original code) should be cached \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Feb 14 at 17:49
1
\$\begingroup\$
    x++;

This is very inefficient.

The intended approach is probably to write a successor function which takes a "perfect"1 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++;
}

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.