CODEWITHSUNDEEP
javaalgorithmrecursion
user16655
user16655

Reputation: 1941

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?

Upvotes: 1

Views: 4304

Answers (6)

xubo peng
xubo peng

Reputation: 1

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

Upvotes: 0

Muhammad Umar Farooq
Muhammad Umar Farooq

Reputation: 521

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

Upvotes: 1

Arafath
Arafath

Reputation: 98

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

Upvotes: 1

גלעד ברקן
גלעד ברקן

Reputation: 23955

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

Upvotes: 1

codebox
codebox

Reputation: 20264

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

Upvotes: 1

amit
amit

Reputation: 178521

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

Upvotes: 8

Related Questions