/**
* 779. K-th Symbol in Grammar
* On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each
* occurrence 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 1-indexed.) (1 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
*/
Here is solution to the problem at github: https://github.com/zcoderz/leetcode/blob/main/src/main/java/recursion/KthSymbol.java
Observation: Need to remember that these indexes start from 1 rather than 0. If we draw out the pattern of indexes on a white board, we will realize that an index k is dependent on the index (k+1)/2 in row above. We also know that the first row is 1, and the value in it is 0. In addition, if parent value is 0, the child value is 0, if it’s an odd index and 1 if its even. Similarly, if parent is 1, the child value is 1, if its an odd index and 0 if its an even index. Thus, we can write a recursive function that has base condition at row 1 returning 0 and handles the above cases.
Here is the code:
public int kthGrammar(int n, int k) {
if (n==1) {
//per the requirements of question the data starts from first row with a 0
return 0;
}
//as you recurse up into a parent row, the kth digit is based in the parent row on parent value at index
//(K+1) / 2
int parent = kthGrammar(n-1, (k+1)/2);
if (parent ==0) {
if ((k%2)==0) {
return 1;
} else {
return 0;
}
} else {
if ((k%2)==0) {
return 0;
} else {
return 1;
}
}
}