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

Note:
1. N will be an integer in the range [1, 30].
2. K will be an integer in the range [1, 2^(N-1)].

My Solution(36ms 12.8MB)

public class Solution {
    public int KthGrammar(int N, int K) {
        return recursiveFind(K - 1);
    }
    
    private int recursiveFind(int k)
    {
        if (k == 0)
        {
            return 0;
        }
        else if (k % 2 == 1)
        {
            return inverse(recursiveFind(k / 2));
        }
        else
        {
            return recursiveFind(k / 2);
        }
    }
    
    private int inverse(int k)
    {
        return k == 1 ? 0 : 1;
    }
}

No.1 Solution(36ms)

public class Solution {
    public int KthGrammar(int N, int K) {
         return helper(N, K-1);
    }
    
  public int helper(int N,int K) {
        if(N==1||K==0) return 0;
        else {
            if(K%2==0) return helper(N-1,K/2);
            else return helper(N-1,K/2) ^ 1;
        }
    }
}

Things to improve

There is not much things to improve in this case, it’s recursive logic and I personally don’t like recursive…

Leave a Reply

Your email address will not be published. Required fields are marked *