Find the K-th Symbol in Grammar

This post is part of my "LeetCode for 1x Developers" series, in which I struggle through LeetCode problems. Sometimes I figure it out, other times I don't. Either way, I give each problem my best shot, and write up my thought process through the challenges

Problem description

Problem on leetcode

On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each occurence of 0 with 01, and each occurrence of 1 with 10.

Given row N and index K, return the K-th indexed symbol in row N. The values of K are `-indexed.

Examples

Input: N = 1, K = 1
Output: 0

Input: N = 2, K = 1
Output: 0

Input: N = 2, K = 2
Output: 1

Input: N = 4, K = 5
Output: 1

Explanation:

row 1: 0
row 2: 01
row 3: 0110
row 4: 01101001

Solution

Intuition

Based on the generating of the rows, I have a feeling there's a mathematical solution to this that's faster than a data structure based algorithm.

To get a feel for what's going on and how I might express it mathematically, I'm going to manually write out the pattern.

Looking at four rows:

0
01
0110
01101001
0110100110010110

I notice that the number of items in each row is 2^N. Which suggests to me there might be some bitwise solution here, which also feels right considering all the 0 and 1 values.

What's more, looking at the way that the pattern stacks (every row N is the beginning of the next row N+1), I don't think N really matters. I think there's something I can do with K.

I'm feeling really good about there being an existing binary operation I can do, but I just can't quite find it or reason about it. I've mentioned this in other posts, but I'm definitely weak when it comes to binary operations and using them for problem solving. This probably comes from my day-to-day in web development, where I'm just not using that kind of problem-solving tool.

So I looked up the discussion answer and I was absolutely on the right track. There is a single arithmetic I can do, in binary, and ignoring N completely.

Answer

Here's a Python one-liner which converts K-1 into its binary representation, counts how many times 1 appears in that representation, and runs a bitwise AND operation on the result.

I couldn't quite grok what was going on and why, but I found this explanation which helps more.

Basically, since we know the prefix of every row N is the same, we only care about how the new row N+1 is going to generate its new string up to K, which will depend on the number K-1.

If we know what K-1 in binary is, we'll know how many times the 01 and 10 pattern toggles back and forth before the number we care about, K.

So we convert it over, count up the 1s, and convert that number into binary. We then run bitwise AND against it to determine the Kth value.

We don't have all the syntactic sugar that comes along with Python, Java, and C++ for bitwise operations, so here's a way to represent it in JavaScript:


var kthGrammar = function(N, K) {
let binary = (K-1).toString(2);
let array = binary.split('');
let count = 0;
for (let i=0; i<array.length; i++) {
if (array[i] === '1') {
count++;
}
}
return count & 1;
};