Recursive digit sum hackerrank solution python
Hackerrank Solution: Recursive Digit SumOriginal Problem We define super digit of an integer \(x\) using the following rules: Given an integer, we need to find the super digit of the integer.
For example, the super digit of \(9875\) will be calculated as: super_digit(9875) 9+8+7+5 = 29 super_digit(29) 2 + 9 = 11 super_digit(11) 1 + 1 = 2 super_digit(2) = 2 You are given two numbers \(n\) and \(k\). The number \(p\) is created by concatenating the string \(n\) \(k\) times. Continuing the above example where \(n=9875\), assume your value \(k=4\). Your initial \(p= 9875\, 9875\, 9875\, 9875\)(spaces added for clarity). superDigit(p) = superDigit(9875987598759875) 5+7+8+9+5+7+8+9+5+7+8+9+5+7+8+9 = 116 superDigit(p) = superDigit(116) 1+1+6 = 8 superDigit(p) = superDigit(8) All of the digits of \(p\) sum to \(116\). The digits of \(116\) sum to \(8\). \(8\) is only one digit, so it's the super digit. Function Description Complete the function superDigit in the editor below. It must return the calculated super digit as an integer. superDigit has the following parameters:
Input FormatThe first line contains two space separated integers, \(n\) and \(k\). Constraints
Output FormatReturn the super digit of \(p\), where \(p\) is created as described above. SolutionWhat is called super digit here, is practically the digital root of a number, which can be implemented recursively, or easier using modulo. We derived the digital root function alreay: \[\text{dr}(n) =1+ (n - 1\pmod{9})\] Using it for our constructed number \(p=k\times n\), where \(\times\) denotes concatinations, we can say: \[\begin{array}{rl} \text{dr}(p) &= \text{dr}(k\times n)\\ &= \text{dr}(n\cdot 10^{0\cdot L(n)} + n\cdot 10^{1\cdot L(n)} + \dots +n\cdot 10^{k\cdot L(n)})\\ &= 1+ ((n\cdot 10^{0\cdot L(n)} + n\cdot 10^{1\cdot L(n)} + \dots +n\cdot 10^{(k-1)\cdot L(n)}) - 1\pmod{9})\\ &= 1+ (k\cdot n - 1\pmod{9}) \end{array}\] With \(L(n)\) denoting the number of digits of numbr \(n\). Since in our problem \(n\) is a string with many many digits, we don't use the number directly, but sum over the digits of \(n\) as \(t=\sum\limits_{i=0}n_i\) first and state \[\text{dr}(p) = \text{dr}(k\times n) = \text{dr}(k\cdot n) = \text{dr}(k\cdot t)\] Implementing this algorithm in Python then is pretty straightforward and bound to \(O(\log n)\) and does not even look at \(p\)!: def superDigit(n, k): return 1 + (k * sum(int(x) for x in n) - 1) % 9 « Back to problem overview Sort 720 Discussions, By: Please Login in order to post a comment
|