title: Given a pair of integers, minimum # of operations performed to reach target N
body: <p>Given a pair of numbers (A, B). 
  You can perform an operation (A + B, B) or (A, A + B). 
  (A, B) is initialized to (1, 1). 
  For any N > 0, find the minimum number of operations you need to perform on (A, B) until A = N or B = N</p>
  
  <p>Came across this question in an interview summary on glassdoor.  Thought through a couple approaches, searched online but couldn't find any articles/answers solving this question.  I have a brute force method shown below, however it must traverse O(2^N) paths, wondering if there is an elegant solution I am not seeing.</p>
  
  <pre><code>def pairsum(N):
      A = 1
      B = 1
  
      return helper(N, A, B, 0)
  
  def helper(N, A, B, ops):
      # Solution found
      if A == N or B == N:
          return ops
  
      # We've gone over, invalid path taken
      if A &gt; N or B &gt; N:
          return float("inf")
  
      return min(helper(N, A + B, B, ops + 1), helper(N, A, A + B, ops + 1))
  </code></pre>