Influence of sign bit


  • 0
    S

    The idea of my solution is quite simple.
    For a given stair number N, I can have at most N/2 chances to climb 2 steps at one time.
    If i choose to climb 2 step for M times and leave the rest climb for 1 step , the total choices I have for this scenario is equal to (choose M from N-M).
    Add all possible M up and it's the answer.

    The problem is , from n=1 to n=43 , my solution gives the perfect answer , but for n>44 , it's wrong . And after trying the test case , I found several negative answers like n=66,87 and so on . I believe that it's because of the signed bit , cause if n=44 , the correct answer is 1134903170 and is already above half of Math.pow(2,31) ,which is max of int
    Anybody know how to get rid of this?

    Below is my code

    public int climbStairs(int n) {
        int choice = n/2;
        int ans = 1;
        for(int i=1;i<=choice;i++){
            ans +=choose(i,n-i);
        }
        return ans;
    }
    
    public int choose(int m,int n){
        int ans = 1;
        for(int i=0;i<m;i++){
            ans *= (n-i);
            ans /= (i+1);
        }
        return ans;
    }

Log in to reply
 

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