# Recursive function and memorization to find minimum operations to transform n to 1

I'm a new, self-taught programmer working on the Google FooBar challenge. I've submitted my answer (code at bottom) and it was accepted, but I'd like suggestions on how to improve my solution.

Challenge: return minimum number of operations to transform a positive integer to 1. Valid operations are: n+1, n-1, or n/2.

My solution I started with a recursive function, but ran into a runtime error with very large numbers. I added memorization using a global variable to store values that had already been computed, but this seems inelegant. (I think it's discouraged to use global variables?)

Suggestions on how I might improve the below solution?

paths = {1:0, 2:1}

def shortest_path(num):
if num in paths:
return paths[num]

if num % 2 == 0:
paths[num] = 1 + shortest_path(num / 2)
else:
paths[num] = min(2 + shortest_path((num+1)/2),
2 + shortest_path((num-1)/2))
return paths[num]

num = int(n)
return shortest_path(num)


Test cases:

n = 15 --> 5
n = 293523 --> 25
n = 191948125412890124637565839228475657483920292872746575849397998765432345689031919481254128901246375658392284756574839202928727465758493979987654323456890319194812541289012463756583922847565748392029287274657584939799876543234568903 --> 1029

• The input number can be up to 309 digits long hence the final test case
• Take a look at this post. If you issue is with larger numbers and you are getting a maximum recursion depth exceeded error then the post might help you. – Mike - SMT Jun 7 '17 at 18:43
• thanks! I actually don't have a problem with recursion - sorry if that was confusing in my post. The code I posted works even with very large numbers. I was just wondering if there's a more elegant way to write it instead of using the global variable paths. – user7875185 Jun 7 '17 at 18:50

Sure, you could remove the global variable by moving the memoization to a decorator and adding a base case scenario to the function.

from functools import wraps

def memoize(func):
cache = {}

@wraps(func)
def inner(*args):
if args not in cache:
cache[args] = func(*args)
return cache[args]

return inner

@memoize
def shortest_path(num):
if num <= 2:
return num - 1

if num % 2 == 0:
return 1 + shortest_path(num/2)

else:
return min(2 + shortest_path((num + 1)/2),
2 + shortest_path((num - 1)/2))


To address the recursion depth error, you could either change sys.setrecursionlimit, or you could rewrite your initial solution to use paths as an argument to avoid the global variable.

def shortest_path(num, paths=None):
paths = paths or {1: 0, 2: 1}

if num in paths:
return paths[num]

if num % 2 == 0:
paths[num] = 1 + shortest_path(num/2, paths)
else:
paths[num] = min(2 + shortest_path((num+1)/2, paths),
2 + shortest_path((num-1)/2, paths))

return paths[num]


Or, as suggested in the other answer, test the number modulo 4 to figure out which path to take and avoid recursion all together.

def shortest_path(n):
count = 0

while n > 1:
if n % 2 == 0:
count += 1
n = n / 2
elif n % 4 == 1 or n == 3:
count += 2
n = (n - 1) / 2
elif n % 4 == 3:
count += 2
n = (n + 1) / 2

return count

• Better yet: from functools import lru_cache (3.2+). However, if I remember correctly, foobar uses Python 2.7, so it's only useful for the general case. – user87373 Jun 7 '17 at 21:50
• @Mego Yep, I only have Python 2.7 on the machine I was working on, so I couldn't test/post that solution. – Jared Goguen Jun 8 '17 at 1:38
• @JaredGoguen Yup it's only 2.7. I tried your solution with a test case (I've edited my original post to include the test case+answer) and am getting a recursion depth error. Any suggestions? – user7875185 Jun 8 '17 at 14:05

The problems you've encountered usually signal that the approach is not the best.

Consider the very first step in your algorithm: you are definite that if the number is even, the best action is $n\rightarrow \frac{n}{2}$ (why?).

Try to apply the same logic one step further. Let $n$ be odd. Either $\frac{n+1}{2}$ or $\frac{n-1}{2}$ is also odd (why?). The best action is to pick that which is even (why?).

As soon as you prove all the why statements, a straight-forward non-recursive algorithm is easy to obtain.