CodingGyan

K-th Symbol in the Grammar

medium Recursion and Backtracking

Problem

Row 1 is the single symbol 0. Every next row is made from the row before it: each 0 becomes 01, and each 1 becomes 10. So row 2 is 01, row 3 is 0110, row 4 is 01101001. Print the k-th symbol (counting from 1) of row n. Do not build the rows: they have 2^(n-1) symbols.

Constraints

  • 1 <= n <= 30
  • 1 <= k <= 2^(n-1)

Examples

Input

4 5

Output

1

Input

3 3

Output

1

Solutions

Best approachTime O(n)Space O(n)

Each symbol in row n has a parent in row n - 1. The first child has the parent's value, the second child has the opposite. So the answer is found by walking up n - 1 rows.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : The k-th symbol.
 * Input   : n and k.
 * Output  : 0 or 1.
 * Approach: Recursion on the parent
 * Time    : O(n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 2: The k-th symbol of row n comes from the symbol (k + 1) / 2 of row n - 1. That symbol made two children.
        static int symbol(int n, long k) {
            if (n == 1) {
                return 0;
            }
            int parent = symbol(n - 1, (k + 1) / 2);
            // Step 3: Odd k is the first child (same as the parent). Even k is the second child (the opposite).
            return k % 2 == 1 ? parent : 1 - parent;
        }

    // This method solves the task. It receives the input and returns the answer.
    static int solve(long a, long b) {
        // Step 1: Go back one row at a time, until row 1, where the answer is known.
        return symbol((int) a, b);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long a = scanner.nextLong();
        long b = scanner.nextLong();
        System.out.println(solve(a, b));
    }
}
Hints (2)
  1. Which symbol is the parent of position k?
  2. When is a child the opposite?