LC-3154 Hard LeetCode

3154. Find Number of Ways to Reach the K-th Stair

Math Dynamic Programming Bit Manipulation Memoization Combinatorics

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 36% Topics: Math, Dynamic Programming, Bit Manipulation, Memoization, Combinatorics

Reading material

Math & Geometry 12 min 1-D Dynamic Programming 16 min Bit Manipulation 10 min

Reference solution (spoiler · python)

# Time:  O(logk)
# Space: O(logk)

# combinatorics
class Solution(object):
    def waysToReachStair(self, k):
        """
        :type k: int
        :rtype: int
        """
        def ceil_log2_x(x):
            return (x-1).bit_length()

        l = ceil_log2_x(k)
        while (1<<l)-k <= l+1:
            l += 1
        fact = [1]*(l+1)
        for i in xrange(len(fact)-1):
            fact[i+1] = fact[i]*(i+1)
        def nCr(n, r):
            if not (0 <= r <= n):
                return 0
            return fact[n]//fact[r]//fact[n-r]

        return sum(nCr(i+1, (1<<i)-k) for i in xrange(l))

Solution from kamyu104/LeetCode-Solutions · MIT