Created
December 22, 2020 05:46
-
-
Save Dante83/c1d74f3fcc6d83cf1691a2d0faa53882 to your computer and use it in GitHub Desktop.
Super Digit Problem on Hackerrank
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function superDigit(n, k) { | |
//This reminds me of a clever math trick, and makes me | |
//wonder if there are more. If you recursively sum a number | |
//and it the final number like this is divisible by 3, | |
//then the number is divisble by 3. Therefore, if n, k times | |
//will just become sum(n) * k and sum(n) * k % 3 === 0 | |
//then the super digit is 3, 6, 9. | |
// | |
//In fact, if the sum of digits is 9, then the super number IS 9. | |
//In fact, there IS a relationship between the sum of the digits | |
//and the base number itself that is solveable in O(1) time. | |
//Yep. O(1). sum_of_digits(n) = (n - 1) % 9 + 1 | |
//It's not even complicated. | |
//Though it is thanks to https://www.sjsu.edu/faculty/watkins/Digitsum369.htm | |
//We also know can see that k sums of the digits of n, can factor | |
//a k out front so that it is actually k * (sum of digits of n) | |
//More importantly, it seems k * (sum of digits of n) == k * sum_of_digits(n) | |
//that is, the sum all the way to a single digit. | |
return Number(((((BigInt(n) - 1n) % 9n + 1n) * BigInt(k)) - 1n) % 9n + 1n); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment