LC-0779 Medium LeetCode

779. K-th Symbol in Grammar

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 47% Topics: Math, Bit Manipulation, Recursion

Reading material

Math & Geometry 12 min Bit Manipulation 10 min Backtracking 14 min

Reference solution (spoiler · python)

# Time:  O(logn) = O(1) because n is 32-bit integer
# Space: O(1)

class Solution(object):
    def kthGrammar(self, N, K):
        """
        :type N: int
        :type K: int
        :rtype: int
        """
        def bitCount(n):
            result = 0
            while n:
                n &= n - 1
                result += 1
            return result

        return bitCount(K-1) % 2

Solution from kamyu104/LeetCode-Solutions · MIT