CODEWITHSUNDEEP
algorithmrecursion
n00bc0d3r
n00bc0d3r

Reputation: 275

Recursion Puzzle

Recently, one of my friends challenged me to solve this puzzle which goes as follows:

Suppose that you have two variables x and y. These are the only variables which can be used for storage in the program. There are three operations which can be done:

Now, you are given two number n1 and n2 and a target number k. Starting with x = n1 and y = n2, is there a way to arrive at x = k using the operations mentioned above? If yes, what is the sequence of operations which can generate x = k.

Example: If n1 = 16, n2 = 6 and k = 28 then the answer is YES. The sequence is:

Operation 1
Operation 1

If n1 = 19, n2 = 7 and k = 22 then the answer is YES. The sequence is:

Operation 2
Operation 3
Operation 1
Operation 1

Now, I have wrapped my head around the problem for too long but I am not getting any initial thoughts. I have a feeling that this is recursion but I do not know what should be the boundary conditions. It would be very helpful if someone can direct me towards an approach which can be used to solve this problem. Thanks!

Upvotes: 2

Views: 377

Answers (4)

Ujjwal Aryal
Ujjwal Aryal

Reputation: 111

In the Vincent's answer, I think the proof is not complete.

Let us suppose two relatively prime numbers suppose n1=19 and n2=13 whose GCD will be 1. According to him, sequence exits if k is multiple of GCD.Since every number is multiple of 1. I think it is not possible for every k.

Upvotes: 0

amit
amit

Reputation: 178431

Assuming a solution exists, finding the shortest sequence to get to it can be done using a BFS.

The pseudo code should be something like:

queue <- new empty queue
parent <- new map of type map:pair->pair
parent[(x,y)] = 'root' //special indicator to stop the search there
queue.enqueue(pair(x,y))
while !queue.empty():
   curr <- queue.dequeue()
   x <- curr.first
   y <- curr.second
   if x == target or y == target:
      printSolAccordingToMap(parent,(x,y))
      return
   x1 <- x+y
   x2 <- x-y
   y1 <- x-y
   if (x1,y) is not a key in parent:    
      parent[(x1,y)] = (x,y)
      queue.enqueue(pair(x1,y))
   //similarly to (x2,y) and (x,y1)

The function printSolAccordingToMap() simply traces back on the map until it finds the root, and prints it.

Note that this solution only finds the optimal sequence if one exists, but will cause infinite loop if one does not exist, so this is only partial answer yet.

Upvotes: 1

Vincent van der Weele
Vincent van der Weele

Reputation: 13177

Maybe not a complete answer, but a proof that a sequence exists if and only if k is a multiple of the greatest common divisor (GCD) of n1 and n2. Let's write G = GCD(n1, n2) for brevity.

First I'll prove that x and y are always integer multiples of the G. This proof is really straightforward by induction. Hypothesis: x = p * G and y = q * G, for some integers p and q.

  • Initially, the hypothesis holds by definition of G.
  • Each of the rules respects the induction hypothesis. The rules yield:
    1. x + y = p * G + q * G = (p + q) * G
    2. x - y = p * G - q * G = (p - q) * G
    3. y - x = q * G - p * G = (q - p) * G

Due to this result, there can only be a sequence to k if k is an integer multiple of the GCD of n1 and n2.

For the other direction we need to show that any integer multiple of G can be achieved by the rules. This is definitely the case if we can reach x = G and y = G. For this we use Euclid's algorithm. Consider the second implementation in the linked wiki article:

function gcd(a, b)
    while a ≠ b
        if a > b
           a := a − b
        else
           b := b − a
    return a

This is a repetitive application of rules 2 and 3 and results in x = G and y = G.

Knowing that a solution exists, you can apply a BFS, as shown in Amit's answer, to find the shortest sequence.

Upvotes: 4

Vikram Bhat
Vikram Bhat

Reputation: 6246

Consider that you have both (x,y) always <= target & >0 if not you can always bring them in the range by simple operations. If you consider this constraints you can make a graph where there are O(target*target) nodes and edge you can find by doing an operation among three on that node. You now need to evaluate the shortest path from start position node to target node which is (target,any). The assumption here is (x,y) values always stay within (0,target). The time complexity is O(target*target*log(target)) using djikstra.

Upvotes: 0

Related Questions