All combinations of 1 + 2 that adds to n

Question

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?

Take a look at [this answer](http://stackoverflow.com/a/4633515/1387612) — janisz, Aug 25 '15 at 11:38

score 8 · Accepted Answer · answered Aug 25 '15 at 11:37

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}}}

score 1 · Answer 2 · answered Aug 25 '15 at 11:54

Here's a simple pseudo-code implementation that should work:

var results = []
function plan(previous, n){
    if (n==0) {
        results.push(previous)
    } else if (n > 0){
        plan(previous + ' step', n-1)
        plan(previous + ' hop', n-2)
    }
}
plan('', 5)

If you want to improve the efficiency of an algorithm like this you could look into using memoization

score 1 · Answer 3 · answered Aug 25 '15 at 16:40

Here's a combinatoric way: think of n as 1 + 1 + 1 ... = n. Now bunch the 1's in pairs, gradually increasing the number of bunched 1's, summing the possibilities to arrange them.

For example, consider 5 as 1 1 1 1 1:

one bunch   => (1) (1) (1) (11) => 4 choose 1 possibilities to arrange one 2 with three 1's
two bunches => (1) (11) (11)    => 3 choose 2 possibilities to arrange two 2's with one 1
etc.

This seems directly related to Wikipedia's description of Fibonacci numbers' "Use in Mathematics," for example, in counting "the number of compositions of 1s and 2s that sum to a given total n" (http://en.wikipedia.org/wiki/Fibonacci_number).

score 1 · Answer 4 · edited May 27 '16 at 07:14

1

This logic is working fine. (Recursion)

public static int numberOfWays(int n) {
    if (n== 1) {
        return 1; // step
    } else if (n== 2) {
        return 2; // (step + step) or jump
    } else {
        return numberOfWays(n- 1)
                + numberOfWays(n- 2);
    }
}

edited May 27 '16 at 07:14

Bo Persson

90,663
31
146
203

answered May 27 '16 at 07:07

Arafath

100
3
9

score 1 · Answer 5 · answered Jul 21 '16 at 17:47

The accepted answer fails performance test for larger sets. Here is a version with for loop that satisfies performance tests at testdome.

using System;

public class Frog
    {
    public static int NumberOfWays (int n)
        {
        int first = 0, second = 1;
        for ( int i = 0; i<n; i++ )
            {
            int at = first;
            first = second;
            second = at + second;
            }
        return second;
        }
    public static void Main (String[] args)
        {
        Console.WriteLine (NumberOfWays (3));
        }
    }

score 0 · Answer 6 · answered Mar 02 '21 at 09:28

C++ code works fine.

   static int numberOfWays(int n)
   {
      if (n == 1) return 1;
      else if (n == 2) return 2;
      else
      {
        static std::unordered_map<int,int> m;

        auto i = m.find(n);

        if (i != m.end())
           return i->second;

        int x = numberOfWays(n - 1) + numberOfWays(n - 2);

        m[n] = x;

        return x;
      }
   }

All combinations of 1 + 2 that adds to n

6 Answers6

Linked