[Solution] Finding perfect number (digits-sum-10) | Microsoft Interview Question
This problem was asked by Microsoft. A number is considered perfect if its digits sum up to exactly
Given a positive integer
n, return the
n-th perfect number.
For example, given
1, you should return
2, you should return
Idea behind the solution
Here a list of the perfect numbers:
19 28 37 46 55 64 73 82 91 109 118 127 136 145 154 163 172 181 190 208 ... 802 901 910 1009 1018
Notice that, the difference of each number is
9. Therefore, looping with a step of 9 and checking if its digits sums up to 10 is faster than just testing every natural number.
Regardless this little tweak, this algorithm still runs in
There must be a way to do it in
O(1), but there are some problems to solve. Consider the following sequence:
... 172 181 190 *199* 208 ...
Notice that 199 is not a correct, yet, summing up
9 will get us
208 which is correct. The same happens for the number
1000, etc. There are some numbers that must be skipped.
The formula to find the
n-th perfect number seems something like:
f(n) = 19 + (n-1) + 9 * g(n)
g(n) is a function that, given
n, will return the number of numbers we should skip because the sum of its digits fails to be 10 like said earlier, but this function is unknown to the author.
Please check the main.js snippet for the solution.
This solution originally posted at: Github by @Murillo2380