Recursive Digit Sum Discussions |

2 weeks ago+ 0 comments

I first did this by calculating n as an int and then iteratively dividing n by 10 to get the least significant digit and add it to a total, multiplying by k before a recursive call to calculate the result's super digit. But that required setting Python's max string conversion much higher than the default. Leaving the digits as strings until the calculation is made worked out nicer. Here is my finished code with a few notes to myself:

# Notes:
# 1. Don't calc p ahead of time both b/c Python's conversion of string to int
#    has a cap (adjust w/ sys.set_int_max_str_digits()) and b/c it's easier to
#    manage the expense of the operation during iteration
# 2. It's a little silly to pass k in the recursive call b/c it's only used
#    on the first iteration, but it seems even sillier to write a superDigit0
#    that only takes an n and is used for recursion.
# 3. It may be possible to determine that n < 1e100000 and k <= 1e5 will give
#    you a p that won't blow the stack by recurring too many times but I didn't
#    do that. To be safe, we could unroll the recursion into a loop.
def superDigit(n: str, k: int) -> int:
        
    def sdc(ns: str) -> int:
        acc = 0
        for ch in ns:
            acc += int(ch)
        return acc * k
        
    total = sdc(n)    
    if total < 10:
        return total
    return superDigit(str(total), 1)

Cookie support is required to access HackerRank