We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
This is a tricky problem. At first sight you would think that to get the first super digit you have to concatenate k times n. However in the edge cases (k = 100000 and len(n) >= 100000 ) you could struggle and take a very long time to solving the first one.
Instead of concatenating, you only have to calculate the superdigit of n and then multiply the result by k.
For example if n=”123” and k = 4: SuperDigit("123", 4) = 1+2+3 + 1+2+3 + 1+2+3 + 1+2+3 = (1+2+3) + (1+2+3) + (1+2+3)+(1+2+3) = 4*(1+2+3)
Taking the last approach your algorithm will be less demanding and therefore faster.
Also, you could do it recursively or in a loop:
Recursively:
defsuperDigit(n,k):# Write your code hereiflen(n)==1:returnint(n)else:superD=sum(map(int,[*n]))*kreturnsuperDigit(str(superD),1)
Recursive Digit Sum
You are viewing a single comment's thread. Return to all comments →
This is a tricky problem. At first sight you would think that to get the first super digit you have to concatenate k times n. However in the edge cases (k = 100000 and len(n) >= 100000 ) you could struggle and take a very long time to solving the first one.
Instead of concatenating, you only have to calculate the superdigit of n and then multiply the result by k.
For example if n=”123” and k = 4: SuperDigit("123", 4) = 1+2+3 + 1+2+3 + 1+2+3 + 1+2+3 = (1+2+3) + (1+2+3) + (1+2+3)+(1+2+3) = 4*(1+2+3)
Taking the last approach your algorithm will be less demanding and therefore faster.
Also, you could do it recursively or in a loop:
Recursively:
Loop: