#1 The Power Sum:

date posted: 2020-04-30


Contents


TMI of the day

  1. Just got new pair of B&O e8 3.0 earphone yay!
  2. Today is start of 4 day holiday in Korea but stuck at home due to covid-19. Hope all are well and everything will come back to normal soon.



Solutions

Recursion problem was pretty hard for me to get a grasp therefore I needed some time to learn what it is exactly before solving problems. If you are struggling with recursion problems I recommend you to read --> What is Recursive algorithm

#1 Solution from Danny Sivan

I could not solve this problem and took me a while to understand solutions. This solution by Danny was most intuitive to me so let me explain the code with an example where X = 10, n = 2.

  • We enter for loop with range(1, 10)
    • when i = 1, ans = 10 - (1^2) = 9
    • since ans = 9 > 0, we go into elif statement and call powerSum(9, 2, 2)
      • Notice that 3rd parameter is i+1, adding one at every iteration to make sure it will end. Just like how we n-1 in factorial
      • we enter for loop with range(2, 9)
      • when i =2, X = 9, ans = 9 - (2^2) = 5
      • ans > 0, so we call powerSum(5, 2, 3)
        • enter for loop with range(3, 5)
        • i =3, X=5, ans = 5 - (3^2) = -4 This time we go into else statement
        • now i=4, X=5 ans = - again so again into else statement
        • we exit for loop and return count = 0.
        • Time to move back up!! return to powerSum(5,2,3)
      • count += powerSum(5,2,3) is same as count += 0
      • now next i in for loop, i =3, X=9 then ans = 9 - (3^2) = 0
      • ans = 0 , count+= 1
      • continue the for loop and all ans will get negative value so we continue until loop is finished.
    • count += powerSum(9,2,2) is same as count += 1
  • Finally we are at i = 2, repeat above process and you will get there....
def powerSum(X, n, start):
    count = 0
    for i in range(start, X):
        ans = X - i ** n
        if ans == 0:
            count += 1
        elif ans > 0:
            count += powerSum(ans, n, i+1)
        else:
            continue
    return count

powerSum(10, 2, 1)

This was my first recursive algorithm problem and it was pretty challenging to understand since it was hard to keep track of all function calls. Hope it will get better and more intuitive in next problem solving exercise.