3-4 short lines in every language


  • 67

    Same simple algorithm written in every offered language. Variable a tells you the number of ways to reach the current step, and b tells you the number of ways to reach the next step. So for the situation one step further up, the old b becomes the new a, and the new b is the old a+b, since that new step can be reached by climbing 1 step from what b represented or 2 steps from what a represented.

    Ruby wins, and "the C languages" all look the same.

    Ruby (60 ms)

    def climb_stairs(n)
        a = b = 1
        n.times { a, b = b, a+b }
        a
    end
    

    C++ (0 ms)

    int climbStairs(int n) {
        int a = 1, b = 1;
        while (n--)
            a = (b += a) - a;
        return a;
    }
    

    Java (208 ms)

    public int climbStairs(int n) {
        int a = 1, b = 1;
        while (n-- > 0)
            a = (b += a) - a;
        return a;
    }
    

    Python (52 ms)

    def climbStairs(self, n):
        a = b = 1
        for _ in range(n):
            a, b = b, a + b
        return a
    

    C (0 ms)

    int climbStairs(int n) {
        int a = 1, b = 1;
        while (n--)
            a = (b += a) - a;
        return a;
    }
    

    C# (48 ms)

    public int ClimbStairs(int n) {
        int a = 1, b = 1;
        while (n-- > 0)
            a = (b += a) - a;
        return a;
    }
    

    Javascript (116 ms)

    var climbStairs = function(n) {
        a = b = 1
        while (n--)
            a = (b += a) - a
        return a
    };

  • 0

    Ha ha, all the languages get together now :-) BTW, the expression a = (b += a) - a; is really nice.

    BTW, Stefan, I post another O(logn) solution in this link and mention this post of yours. I hope it is Ok. :-) Just let me know if you have any opinion.


  • 1
    L

    They are so elegant and beautiful.
    You did such a greate job for those problems in leetcode.
    Your posts are usually my first choice when I got stuck by some problems.
    Thanks for sharing your ideas


  • 0
    O

    maybe one redundant iteration in python


  • 0

    Not just in Python but in all of them :-). But I'd have to do something like range(n-1) instead of range(n), and I'd have to handle the distinction between n=0 and n=1. So it would be more code and more complicated.

    Well, apparently the OJ's test cases don't include n=0. But it could (and I think it should). Anyway, relying on n=0 not being asked, in C&Co I could simply change n-- to --n and return b instead of a. But at least here, I wouldn't want to do that because I wanted to have the same algorithm in every language.


  • 0
    Q

    why some n-->0, some n--.
    for case n<=0, what's a reasonable answer, 1 or 0?
    I prefer 1 for n<=0, since the climing is finished, there is one way -- not climing, similar with factorial(0)=1.


  • 0

    n-- > 0 when the language doesn't allow n-- (Java and C# don't autoconvert ints to bools).

    Is the code not clear about n=0? It does return 1 then. And about n<0 I'd say that would be invalid nonsense input.


  • 1
    Q

    there is redundancy in code blow

    a, b = b, a + b
    

    it could be faster by remove it

    a, b = 1, 1+n%2
    for i in range(int(n/2)):
        a += b
        b += a
    return a

  • 0
    R

    @StefanPochmann But that approach is way faster. It does it in 29ms.

    def climbStairs(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n==0:
                return 0
            if n==1:
                return 1
            if n==2:
                return 2
            x=[]
            x.extend([1,2])
            for i in xrange(2,n):
                x.append((x[i-1]+x[i-2]))
            return x[n-1] 
    

  • 0

    @kaddu said in 3-4 short lines in every language:

    But that approach is way faster. It does it in 29ms.

    No it isn't and no it doesn't.

    I just submitted it three times and it got accepted in 82, 35 and 55 ms.

    Also, I then renamed it to climbStairs2 and added this which does the work a thousand times:

    def climbStairs(self, n):
        for _ in range(1000):
            answer = self.climbStairs2(n)
        return answer
    

    That then got accepted in 242, 246 and 199 ms. The same with my solution got accepted in 132, 108 and 106 ms. That pretty clearly shows that (1) my solution is faster and (2) our solutions (run once instead of 1000 times) take far less than 1 ms so the acceptance times we're seeing are almost exclusively judge/system time which varies a lot so you can't meaningfully compare our solutions by them (unless you scale them up like I just did).

    Or you could do some local testing:

    >>> class Solution(object):
        def climbStairs(self, n):
            a = b = 1
            for _ in range(n):
                a, b = b, a + b
            return a
    
    >>> climbStairs = Solution().climbStairs
    >>> from timeit import timeit
    >>> timeit(lambda: [climbStairs(n) for n in xrange(46)], number=100000)
    5.808989976049606
    >>> timeit(lambda: [climbStairs(n) for n in xrange(46)], number=100000)
    5.78949133281793
    

    The same with yours took 15.796894891994867 and 15.71157097576446 seconds.

    Also, we're using the exact same algorithm and your way is more complicated. So one should expect it to be slower and be surprised if it appears to be faster in some test and really dig deeper before claiming that it is faster.


  • 0
    R

    @StefanPochmann I understand that you algorithm was pretty efficient than mine and with no offence I asked the query because I was pretty confused with the judge/system time. I just didn't find it saying anywhere that we are not supposed to judge our code on the basis of time. That written somewhere would be really helpful. Anyway, your codes are really inspiring and help alot.


  • 1

    @kaddu Yeah, one needs to play around with it a bit to get a feeling for how reliable timings are. That's true in general, though, not just on LeetCode. You can see that even in my local testing, where I'm quite sure I don't have much extra costs and variations, I still did it twice.


Log in to reply
 

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