O(log(n)) way in Java, split half


  • 0

    I posted my solution there http://disq.us/p/1m5cqqi, as there are a collection of discussions.

    Someone mentioned that by derive matrix you can get:
    f(2n) = f(n)^2 + f(n-1)^2
    f(2n+1) = f(n)^2 + 2*f(n) * f(n-1)


    I sort of derived the same equation from a different approach:

    The climbing stair question: You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
    https://leetcode.com/proble...

    In the end I realize that f(n) = f(n-1) + f(n-2) and it is exactly fibonacci number.

    Thus thinking about climbing stairs, I wish there is a way to always divide the process half in order to speed up calculation:

    Think about climbing two steps as "binding" a couple of one step together. Then when dividing half, you want to make the two halves mutually exclusive events, then you can simply multiply two halves as the answer.

    Then the only thing matter is if the center "1 step"(s) is either separate or bind together with the step before or after to become a "2 step".

    For even number: the center two "1"s are either bind together or separate.
    f(6) = 111111 = 111 | 111 + 11 | (11) | 11 = f(3)^2 + f(2)^2

    For odd number: the center one "1" is either separate, bind together with before, or bind with after.
    f(7) = 1111111 = 111 | 1 | 111 + 11 | (11) | 111 + 111 | (11) | 11 = f(3)^2 + 2*f(3)*f(2)

    By thinking this way and you can see the generalized case:
    f(2n) = f(n)^2 + f(n-1)^2
    f(2n+1) = f(n)^2 + 2*f(n) * f(n-1)

    class Solution {
        public int climbStairs(int n) {
            // fn = fn-1 + fn-2  // fibonacci
            // split half till end, O(log(n)), http://disq.us/p/1m5cqqi
            // f(2n) = f(n)^2 + f(n-1)^2, f(2n+1) = f(n)^2 + 2*f(n)*f(n-1)
            if (n == 0) return 1;
            else if (n == 1) return 1;
            else if (n == 2) return 2;
            else {
                if (n % 2 == 0) {
                    return climbStairs(n/2)*climbStairs(n/2) + climbStairs(n/2-1) * climbStairs(n/2-1);
                } else {
                    return climbStairs((n-1)/2)*climbStairs((n-1)/2) + 2*climbStairs((n-1)/2) * climbStairs((n-1)/2 - 1);
                }
            }
        }
    }
    

Log in to reply
 

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