Determining if an answer can be generated

How can I improve my code below for the following question? While it works, I am not satisfied with how it looks; I was hoping I can somehow keep it recursive, and have the ans filled up inside the function, and reduce the number of return statements that I have. Treat this like an interview problem.

Worst case: \$O(2^n)\$? Please verify and elaborate

Space complexity: \$O(1)\$


Problem:


You have four integers, a, b, c, d, and the goal is to make a == c and
b == d, given that you are only allowed to do a+b, b, or a, b+a at any
given transformation.


For example, if a = 1, b = 2, c = 3, and d = 8
you can start with (1, 2), change it to (3, 2), change that to (3, 5),
and then change that again to (3, 8) to succeed.

static int ans = 0;
  public static void ablehelper(int a, int b, int c, int d){
      if(a != c && (b + a) > c){
          return;
      }
      if(b != d && (b + a) > d){
          return;
      }
      if(a == c && b == d){
          ans = 1;
          return;
      }
      ablehelper(a + b, b, c, d);
      ablehelper(a, b + a, c, d);

  }
  public static String able(int a, int  b, int c, int d){
      ablehelper(a, b, c, d);
      if(ans == 1){
          return "Able to generate";
      }else{
          return "Not table to generate";
      }
  }

Update:

As per one of the algorithms described below, I wrote this:

public static String betterSolution(int a, int b, int c, int d){
          while( c > a || d > b){
              if(c > d){
                  c = c-d;
              }else{
                  d = d-c;
              }
          }
          if( c == a &&  d == b){
              return "Able to generate";
          }else{
              return "Not able to generate";
          }
      }

This is an interesting problem! You kept our chatroom quite occupied with discussing this question for quite a while :)

Your approach is interesting but it has one big flaw:
You're starting from the wrong direction!

Instead of starting from a and b, start from c and d. Ask yourself this question: What are the ways to reach that number?

Consider this problem: (I will use the notation a, b --> c, d)

4, 5 --> 15, 19

What has to be the step before 15, 19? Which number was added to which?

Was it 15, x or was it x, 19? x, 19 would be nuts as 15 is less than 19. Therefore, we know that it was 15, x. And x must be 4, as 15 + 4 = 19.

By continuing to subtract the biggest number with the lowest number, we can find out all the possible inputs that can produce these two numbers.

15, 19
15, 4
11, 4
7, 4
3, 4
3, 1
2, 1
1, 1

As a, b was 4, 5, we can see already at 15, 4, that this is not possible because 4 3, 8:

3, 8 <--- 8 is bigger, so decrease it by 3
3, 5 <--- 5 is bigger, so decrease it by 3
3, 2 <--- 3 is bigger, so decrease it by 2
1, 2 <--- 2 is bigger, so decrease it by 1
1, 1

Wait, what's that!? 1, 2 is in the list!? It's our lucky day! We've found a matching a, b! So this will return true.

I will leave the fun part of implementing the code up to you :) I hope your understand this approach.

As for the time complexity: Significantly faster than your current approach. As for the real time complexity, ask @rolfl.

StackExchange Code Review Q#49418, answer score: 15