algoadvance

Leetcode 779. K

Problem Statement

The problem is from LeetCode and states:

We build a table of n rows (1-indexed). We start by writing 0 in the 1st row. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 0 with 10. Given two integers n and k, return the k-th indexed symbol in the n-th row. (The value of k is 1-indexed.)

Example

1. Input: n = 1, k = 1
   • Output: 0
   • Explanation: First row is “0”.
2. Input: n = 2, k = 1
   • Output: 0
   • Explanation: Second row is “01”.
3. Input: n = 2, k = 2
   • Output: 1
   • Explanation: Second row is “01”.

Constraints:

• ( 1 \leq n \leq 30 )
• ( 1 \leq k \leq 2^{(n-1)} )

Clarifying Questions

1. Output Format: Should the result always be either a 0 or 1?
   • Yes, since the only possible values are 0 or 1.
2. Recursive Nature: Is there a simpler recursive approach to derive the value rather than constructing the entire rows?
   • Yes, this problem can be tackled using a recursive approach by leveraging the properties of the previous rows to the current row.

Strategy

1. Recursive Insight: The problem can be efficiently solved using recursive logic.
   • Each time we encounter a new row, the symbols are determined based on the previous row.
   • If a symbol in the previous row is 0, it turns into 01 in the next row.
   • If a symbol in the previous row is 1, it turns into 10 in the next row.
2. Binary Properties:
   • If k is odd, look at the left (first half of the row).
   • If k is even, look at the right (second half of the row).

By analyzing further, we can come to the conclusion:

• k in the n-th row is determined by ceil(k/2) in the (n-1)-th row.
• The transformation depends on whether k is odd or even.

Code

Here is a C++ implementation of the solution:

class Solution {
public:
    int kthGrammar(int n, int k) {
        // Base case
        if (n == 1) return 0;
        
        // Determine the length of the previous row
        int length_of_prev_row = 1 << (n - 2); // 2^(n-2)
        
        if (k <= length_of_prev_row) {
            // The first half of the row
            return kthGrammar(n - 1, k);
        } else {
            // The second half of the row
            return !kthGrammar(n - 1, k - length_of_prev_row);
        }
    }
};

Time Complexity

The time complexity for this recursive approach:

• We divide the problem size by 2 with each recursive call.
• This leads to a time complexity of (O(\log k)), which simplifies to (O(n)) because (k) can be as large as (2^{(n-1)}).

The space complexity is also (O(n)) due to the recursion stack.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?