# 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";
}
}

• Are all four inputs guaranteed to be non-negative? – 200_success May 10 '14 at 23:31
• @200_success yes; give me a hand with the time complexity of what I have written(I know an O(n) algorithm that I figured out, but I am upset at not being able to derive the worst case of my solution above) – bazang May 11 '14 at 6:26
• bazang, is your new algorithm intended to permit when any of a, b, c, or d are equal to 0? If so, it does not correctly handle the input a=0, b=1, c=1, d=1. It loops forever. But yes, this is a faithful interpretation of Simon's algorithm. It still takes exponential time on the input a=1, b=1, c=n, d=1, though. To fix that would require a different algorithm such as the one suggested in my answer. – Gankro May 11 '14 at 21:29

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 < targetB.

Doing this for your example of 1, 2 --> 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.

• Using the obvious implementation, this takes $O(1)$ space, but is still exponential in the size of the input. The worst-case being a=1, b=1, c=n, d=1. The algorithm will count down from $n$ to $1$. This is, of course, the size of the actual solution to the problem. However it's not clear that that is a lower-bound. – Gankro May 11 '14 at 4:45
• @Ganko Since each step has one solution, the whole algorithm would be $O(n)$ where $n$ is the larger of $c$ and $d$. – David Harkness May 11 '14 at 5:10
• Yes, which is exponential in the size of the input. – Gankro May 11 '14 at 5:38
• @Simon André Forsberg I still would like to know what the worst case complexity for my problem is. is it O(2^n), if yes, why, if no, why not? – bazang May 11 '14 at 6:25
• What do you do if d = 2 * c? In the next step you would get c, c. I think this problem can be extended to d = n * c where you would eventually end up with the c,c combination. On short glance I would say that these pairs are not solvable. (Apart from the trivial solution where c=1) – Nobody May 14 '14 at 8:46

## Complexity Discussion

You ask whether the complexity is $O(2^n)$.

If this were really an interview question, and you were asked to discuss the complexity of your solution, the answer you should give is something along the lines of:

Complexity in computing is designed to describe how a solution to a problem scales as you change the volume of the input data. Normally, two different types of complexity are key, Time Complexity, and Space Complexity. For Time Complexity, if the complexity is $O(n)$ and the input data doubles, then the time will double. If the complexity is $O(n^2)$, then when the input doubles, the time will quadruple.

Since, in this problem, there are only ever 4 input values, there is no way to meaningfully discuss Time or Space complexity. It is meaningless. The input data does not ever scale.

By suggesting that the complexity is $O(n^2)$ you are showing a gap in your knowledge of complexity. For a start, there is no n defined in your problem... what is it?

Also, if time complexity really was significant/applicable, a complexity of $O(2^n)$ is huge. Every time you add an input value, you double the execution time. So, for example if you currently had 4 input values, and it takes 4 seconds, then it will take 8 seconds with 5 input values, and 16 seconds with 6 input values, and, with 20 input values, it will take ..... almost a day. and 24 values will take a month, and 30 values... 8.5 years ....

• I would -1 this one if I had the rep. Of course there is time complexity! "In mathematics, big O notation describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions." In this case you can provide an O in terms of the input values, a, b, c, and d. Is it O(a^2)? O(3^c)? Of course not. But note the algorithm is very slow for e.g. able(1,1,1000000,1), so maybe something like O(max(c,d)/min(a,b) - min(a,b)). – Claudiu May 11 '14 at 1:38
• Also note: "[...] the complexity of primality tests and multiplication algorithms can be measured in two different ways: one in terms of the integers being tested [...] and one in terms of the number of [bits] in those integers [...] if n is the integer being tested for primality, trial division can test it in Θ(n^(1/2)) arithmetic operations; but if n is the number of bits in the integer being tested for primality, it requires Θ(2^(n/2)) time. In the fields of cryptography and computational number theory, it is more typical to define the variable as the number of bits in the input integers." – Claudiu May 11 '14 at 1:39
• @Claudiu - you are right .... but, the point is that you have to define what the complexity is in the order of .... and, in computing, O(n) is normal for n to refer to input dataset size – rolfl May 11 '14 at 1:40
• @Claudiu - I invite you to the 2nd monitor chat room, where this was discussed a fair amount an hour or so ago: chat.stackexchange.com/rooms/8595/the-2nd-monitor – rolfl May 11 '14 at 1:41
• If the input is numbers, then commonly the input size is the number of bits required to encode those numbers. This is very, very standard for algorithms that manipulate numbers. – G. Bach May 11 '14 at 11:45

EDIT: Here is a linear time algorithm based on an optimization to Simon's!

## Algorithm

We assume that the input consists of non-negative integers.

Simon's algorithm is an excellent improvement which does great on problems whose solution "alternates" between the two choices frequently, but performs very poorly for solutions which consist of long "streaks" of making the same choice. This is observed in the solution a=1, b=1, c=n, d=1. Simon's algorithm will count down from $n$ to $1$, which is an exponential running time (in terms of bits required to represent the input).

The solution is then to "compress" these paths.

As with Simon's algorithm, we start with c and d, and identify which is the largest. Say it's c (if not, simply apply symmetric reasoning). So then the previous step in any solution must have been to increase c by d. However, unlike Simon's algorithm, we will identify how many times this was the case. This is simple: it's just how many times larger c is than d, or c/d (using integer division). So instead of recursing on c-d, d, we then recurse on c - d*(c/d), d.

However we may now possibly "skip over" the starting position (a,b) we are seeking. This is, fairly easy to detect, though. We just return if b==d and (c - a)%d == 0.

Finally, a corner case not mentioned by Simon, which is necessary to consider when you allow $0$ as valid input (Simon does not, so his algorithm is fine): c == d. If this is the case, then there are in fact two valid previous steps: 0, d and c, 0. We must check if our solution is either of these, and then simply terminate.

## Analysis

At each step, one of our two numbers shrinks by at least half (the worst case being when $c = 2d - 1$). Our algorithm terminates at worst when both numbers are 0. Thus, after $O(\log c + \log d)$ time the algorithm must terminate. This is linear in the size of the input.

This can be done in $O(1)$ space using a loop or tail recursion.

## Code

Finally, here is my implementation in Java (compiled and tested for a few inputs)

public static boolean hasSolution(int a, int b, int c, int d){
if(a < 0 || b < 0 || c < 0 || d < 0){
throw new IllegalArgumentException("Negative inputs are not allowed");
}

if(c == 0 || d == 0){
//This is a fixed point, an inescapable blackhole!
return a == c && b == d;
}

while(true){
if(a == c && b == d){
//We're done!
return true;
}else if(c == d){
//weird corner case
return hasSolution(a, b, 0, d) || hasSolution(a, b, c, 0);
}else if(c > d){
int next = c - d*(c/d);
if(next < a){
//we're going to overshoot!
// Check if there exists a k such that
// a + k*d == c
return b == d && (c - a)%d == 0;
}else{
//recurse!
c = next;
}
}else{
//No really, c is > d
int temp;
temp = a; a = b; b = temp;
temp = c; c = d; d = temp;
}
}
}


# Original Answer (a brief analysis of the OP's algorithm):

Here is a really bad example for your program: a=1, b=1, c=999999999, d=1

Your program will continually follow the first recursive step until it has counted from a to c, and then return true.

Your program will run in $\Omega(c)$ time, which most would generally regard as "exponential", as it is exponential in the number of bits required to represent the input. In addition, your program will require $\Omega(c)$ space, as the first branch of your recursion cannot be tail-call optimized, so each iteration will push an entire stack-frame on top. So your space consumed is also exponential in the actual input size. Naive translation of this algorithm to be non-recursive (with a loop and a stack) would not solve this problem.

Note that this is only for this input. I have no idea what the true asymptotic running time of this algorithm is, because weirder inputs have weirder behaviours, and it's not clear to me what exactly the true worst case is. You're essentially doing depth-first search on a binary tree that can be something like $O(c/b + d/a)$ nodes deep. So that's definitely the worst-case on space (as exhibited by my example), but running time is unclear. The number of nodes in such a tree can be as much as $2^{depth}$, so maybe there's an input that exhibits $\Omega(2^{c+d})$ running time, (which is doubly exponential in input size) but I'm unclear as to how to trigger that (if possible). I'm inclined to think that there aren't nearly that many nodes in the tree, as the "middle" of the tree thins out much more rapidly than the sides (there are definitely always branches that are $O(\log{(c + d)})$ deep. You can always force the algorithm to search the whole tree by making the answer "no", though (assuming @janos's improvement that terminates when the correct answer is found).

If I had to guess, something like a=2, b=2, c=2n+1, d=2n+1 exhibits the worst-case behaviour.

I believe the recurrence tree would something like the left- and right-most branches being size $n$, the next most outward branches are size $n/2$, then $n/4$, and so on (halving) until we reach two middle branches of size $1$. This gives us about $4n$ nodes, which is assymptotically the same as $n$. Thus I conjecture the algorithm "only" runs in exponential time and space in the worst case.

Simon's answer is, regardless, much better, and is also much easier to analyse (though it's still exponential in the worst-case).

• Why are you fixated on defining $n$ to be the number of bits required to store the initial values? You said "the size of the inputs", but this is but one definition of size--the one I see used the least. – David Harkness May 11 '14 at 5:23
• @DavidHarkness Can you show me a place where the running time of an algorithm is not in terms of the size of the input? I am honestly at a loss for anywhere where this is not the case. – Gankro May 11 '14 at 5:35
• @DavidHarkness note that failing to treat a single number $n$ as actual only $\log n$ bits implies a polynomial time solution to the knapsack problem (which is NP-Complete), as there exist solutions which run in linear time with respect to the size of the knapsack (a single integer in the input). This would be an exceptional breakthrough in the field of computer science! – Gankro May 11 '14 at 5:42
• You say that I neglect the case where c == d, and yet you say that Our algorithm terminates at worst when both numbers are 1, in which case you also neglect the possibility of the starting numbers 0, 1 for those cases. I assumed that all values where positive integers, in which case c == d will never have a solution. – Simon Forsberg May 11 '14 at 11:20
• This answer has just been auto-flagged for excessive editing. Please try to keep the edits to a minimum; each one bumps the question. – Jamal May 11 '14 at 13:57

## Making it pure recursive

It's fairly straightforward to turn your implementation into pure recursive:

public boolean ablehelper(int a, int b, int c, int d) {
if (a != c && (b + a) > c) {
return false;
}
if (b != d && (b + a) > d) {
return false;
}
if (a == c && b == d) {
return true;
}
return ablehelper(a + b, b, c, d) || ablehelper(a, a + b, c, d);
}


You can simplify that a little bit:

if (a > c || b > d) {
return false;
}
if (a == c && b == d) {
return true;
}
return ablehelper(a + b, b, c, d) || ablehelper(a, a + b, c, d);


## Recursive, but going from the other direction

As Simon pointed out, it's better to think from the other direction: realize that the step before arriving at the solution would have one of these set of values:

1. a = c , b = d - c, c , d - c
2. a = c - d, b = d , c - d, d

That is, in the first case, you reach the solution by taking (a, a + b), and in the second case by taking (a + b, b).

Thinking in this direction will help, because you don't need to explore the entire space of adding up a lot of small numbers that may or may not reach the right pairing. So this way you will find the solution faster:

if (a > c || b > d) {
return false;
}
if (a == c && b == d) {
return true;
}
if (c > d) {
return ablehelper(a, b, c - d, d);
}
return ablehelper(a, b, c, d - c);


Keep in mind that a recursive solution is not the best way here. You will inevitably get StackOverflowError with large enough N in (1, 1, N, 1), for example on my PC with default settings 9999 is large enough. You can refactor to use a loop instead of recursion, that will work for much larger values of N too.

## Recursive, going from the other direction, on steroids

Building on @Gankro's answer, notice that when c = X + Y * d, then instead of recursing on (c - d, d) many times, we could do the same in one step: (c - d * Y, d). With this the last lines of the implementation can be improved with:

if (c > d) {
return ablehelper(null, a, b, c - d * Math.max(1, c / d - 1), d);
}
return ablehelper(null, a, b, c, d - c * Math.max(1, d / c - 1));


We don't know X and Y, but Y must be between c / d and c / d - 1. So we take c / d - 1, so that we don't overshoot and subtract too much. The Math.max is there is to make sure the multiplier is at least 1.

## Complexity

If I can figure out to calculate this properly, I will post again. For now I'd rather not say something stupid. I would just say that, perhaps the worst case is when you cannot take shortcuts, and have to alternate subtraction from c and d, like with a set of Fibonacci numbers, for example going from (c, d) = (21, 34) to (1, 1):

21, 34
21, 13
8, 13
8, 5
3, 5
3, 2
1, 2
1, 1


But how to express and estimate the complexity of this based on (a, b, c, d), I don't know...

• what about the worst case analysis? – bazang May 10 '14 at 20:49
• @SimonAndréForsberg: ? The original problem is also recursive, this just improves it by not putting the answer in a global variable – Claudiu May 11 '14 at 1:28
• I would just like to note that this also has the substantial improvement that it terminates as soon as it knows the answer. The OP's answer will search the entire tree of possible combinations, even if it found the answer is "yes" after one step. @SimonAndréForsberg's answer is, of course, vastly better. – Gankro May 11 '14 at 4:38