user16655 user16655 - 4 months ago 23
Java Question

All combinations of 1 + 2 that adds to n

I am trying to solve this question as the preparation for a programming interview:


A frog only moves forward, but it can move in steps 1 inch long or in jumps 2 inches long. A frog can cover the same distance using different combinations of steps and jumps.

Write a function that calculates the number of different combinations a frog can use to cover a given distance.

For example, a distance of 3 inches can be covered in three ways: step-step-step, step-jump, and jump-step.


I think there is a quite simple solution to this, but I just can't seem to find it. I would like to use recursion, but I can't see how. Here is what I have so far:

public class Frog {

static int combinations = 0;
static int step = 1;
static int jump = 2;
static int[] arr = {step, jump};

public static int numberOfWays(int n) {
for (int i = 0; i < arr.length; i++) {
int sum = 0;
sum += arr[i];
System.out.println("SUM outer loop: " + sum + " : " + arr[i]);
while (sum != 3) {
for (int j = 0; j < arr.length; j++) {
if (sum + arr[j] <= 3) {
sum += arr[j];
System.out.println("SUM inner loop: " + sum + " : " + arr[j]);
if (sum == 3) {
combinations++;
System.out.println("Combinations " + combinations);
}
}
}
}
}
return combinations;
}

public static void main(String[] args) {
System.out.println(numberOfWays(3));
}
}


It doesn't find all combinations, and I think the code is quite bad. Anyone have a good solution to this question?

Answer

Think you have an oracle that knows how to solve the problem for "smaller problems", you just need to feed it with smaller problems. This is the recursive method.

In your case, you solve foo(n), by splitting the possible moves the frog can do in the last step, and summing them):

foo(n) = foo(n-1) + foo(n-2)
            ^         ^
         1 step    2 steps

In addition, you need a stop clause of foo(0) = 1, foo(1)=1 (one way to move 0 or 1 inches).

Is this recursive formula looks familiar? Can you solve it better than the naive recursive solution?


Spoiler:

Fibonacci Sequence

Comments