Kth Symbol
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.recursion;
import java.util.*;
/ * Problem: Kth Symbol * Group: 07. Recursion */ / * ============================================================================================ * PROBLEM: K-th Symbol in Grammar * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * We build a table of rows of 0s and 1s. * - Row 1 is "0". * - To generate Row A from Row A-1: * Replace every '0' with "01". * Replace every '1' with "10". * * Task: Given row A and index B (1-based), find the B-th symbol. * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * Let's observe the growth: * Row 1: 0 * Row 2: 01 * Row 3: 0110 * Row 4: 01101001 * * Key Observations: * 1. The length of Row A is 2^(A-1). * 2. The first half of Row A is exactly the same as Row A-1. * 3. The second half of Row A is the complement (inverse) of Row A-1. * * Recurrence Relation: * Let f(A, B) be the value at Row A, Index B. * Let 'mid' be the length of the previous row = 2^(A-2). * * - If B <= mid: The value lies in the first half. * f(A, B) = f(A - 1, B) * * - If B > mid: The value lies in the second half. * f(A, B) = NOT f(A - 1, B - mid) * (Mathematically: 1 - f(A - 1, B - mid)) * * Base Case: * - If A = 1, return 0. * * --------------------- * 3. Constraints & Complexity Analysis * --------------------- * Constraints: * 1 <= A <= 20 * 1 <= B <= 2^(A-1) * * Time Complexity: * O(A) - In each step, we reduce the row index A by 1. Since A <= 20, this is O(1) in practice. * * Space Complexity: * O(A) - Recursion stack depth is equal to A. * * --------------------- * 4. Input / Output Format * --------------------- * Input: * - Integer A (Row number). * - Integer B (Index, 1-based). * * Output: * - Return 0 or 1. * * --------------------- * 5. Examples * --------------------- * Input 1: A = 2, B = 1 * Output 1: 0 * Explanation: Row 2 is "01". 1st element is 0. * * Input 2: A = 2, B = 2 * Output 2: 1 * Explanation: Row 2 is "01". 2nd element is 1. * * Input 3: A = 4, B = 5 * Output 3: 1 * Explanation: * Row 3: 0110 * Row 4: 0110 1001 * Index 5 is the start of the second half, which is the inverse of Row 3's start (0) -> 1. * * ============================================================================================ */ public class KthSymbol { public int solve(int A, int b) { // TODO: Implement solution return 0; } }