Leetcode 0779 K-th Symbol in Grammar

Problem statement

https://leetcode.com/problems/k-th-symbol-in-grammar/

Solution

Actually, it can be shown, that k-th symbol in our string will depend on parity of number of ones in binary representation of number k. Also we need to take into account that we start with index 1, not 0, so finally solution can be written as the following oneliner.

Complexity

Time and space complexity is O(log k).

Code

class Solution:
    def kthGrammar(self, N, K):
        return int(bin(K-1).count("1") % 2 == 1)