Skip to content

Instantly share code, notes, and snippets.

@Dante83
Created December 22, 2020 05:46
Show Gist options
  • Save Dante83/c1d74f3fcc6d83cf1691a2d0faa53882 to your computer and use it in GitHub Desktop.
Save Dante83/c1d74f3fcc6d83cf1691a2d0faa53882 to your computer and use it in GitHub Desktop.
Super Digit Problem on Hackerrank
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