1

I encounter a strange problem:

a digital root function is something looks like this:

digital_root(493193)
=> 4 + 9 + 3 + 1 + 9 + 3
=> 29 ...
=> 2 + 9
=> 11 ...
=> 1 + 1
=> 2

and my answer is:

def digital_root(n):
    k = 10
    while k > 9:
        k = reduce(lambda x,y: int(x)+int(y), list(str(n)))
    return k

I set k to 10 so that it will directly go in to the loop. But the online judge says it costs too much time.

and I try another solution:

def digital_root(n):
    while n > 9:
        n = reduce(lambda x,y: int(x)+int(y), list(str(n)))
    return n

then the problem solved. I can figure out what's the difference between these two codes

By the way, I use the codewars online judge.

SoulerTsai
  • 87
  • 2
  • 10

2 Answers2

4

problem here is that you have an infinite loop and your first solution is not slow but just wrong

def digital_root(n):
    k = 10
    while k > 9:
        k = reduce(lambda x,y: int(x)+int(y), list(str(n)))
    return k

the first reduce gives 29. so k > 9, and it does it again, but since you're not reinjecting k but reusing n, you get 29 again.

the second solution is correct because it changes & reinjects n as long as it is greater than 9 (and doesn't enter in the loop if n <= 9 because in that case digital root is the number itself).

Edit: for that particular case you don't need reduce at all. That code is clearer and probably faster:

def digital_root(n):
    while n > 9:
        n = sum(int(x) for x in str(n))
    return n

(sums all int-converted digits of n in a generator comprehension)

Jean-François Fabre
  • 137,073
  • 23
  • 153
  • 219
  • Probably could still be faster, though. http://stackoverflow.com/questions/14939953/sum-the-digits-of-a-number-python – OneCricketeer Feb 04 '17 at 16:13
  • yes, converting to string is probably not the best thing to do with all the back & forth conversions, I could have thought of that... – Jean-François Fabre Feb 04 '17 at 16:32
  • Thank you all, actually this is faster ` def digital_root(n): return n%9 or n and 9 ` I saw this code on codewars, very clever! – SoulerTsai Feb 05 '17 at 01:47
1

You can do, also, something like this example:

def reduce_root(num = 0):
    if isinstance(num, int):
        return [k for k in str(num)]
    else:
        raise Exception("input number must be an integer!")

def digital_root(num = 0):
    number = reduce_root(num)
    print("Number: {}".format(num))
    while True:
        if len(number) == 1:
            break
        else:
            print("=> {}".format(" + ".join(k for k in number)))
            s = sum(int(k) for k in number)
            print("=> {}".format(s))
            number = reduce_root(s)

Output:

digital_root(100245)

Number: 100245
=> 1 + 0 + 0 + 2 + 4 + 5
=> 12
=> 1 + 2
=> 3
Chiheb Nexus
  • 9,104
  • 4
  • 30
  • 43