Why doesn't this combinations solution work?


  • 0
    A

    This solution seems to work for 20 test cases but breaks for input of 35, I don't quite understand why.

    Here's the logic behind it:

    1. To climb n stairs we have the option of taking 0 to n/2 double steps.

    2. for each number of double steps that we can take we have k options of how to arrange the single steps that we take in between those double steps. We can work out this number using the Combinatorics formula.

    https://en.wikipedia.org/wiki/Combination

    So for example:

    We want to climb 35 steps. We can climb them all taking 1 step at a time. Or we can climb them taking 1 double step and 33 single steps. or we can take 13 double steps and 9 single steps.

    So lets say we want to calculate how many distinct ways we can take 13 double steps and 9 single steps.

    We know that we will be taking 22(13 double + 9 single) steps altogether.

    So now we just want to find the number of orderings for arranging our double and single steps.

    Which should be equal to 22 chose 9. Hence the code:

    public int climbStairs(int n) {
        int sum = 1;
        int singles;
        for(int twos = n/2; twos > 0; twos--){
            singles = n - twos * 2;
            sum = sum + choose(twos + singles, singles);
        }
        return sum;
    }
    
    public int choose(int n, int r){
        if(r == 0) return 1;
        return choose(n, r-1)*(n-(r-1))/(r);
    }

  • 0
    A

    Got it, the integers in the choose method are overflowing....


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.