Tap here to switch tabs
Problem
Submissions

Problem: Find Kth Bit in Nth Binary String

Try to solve the Find Kth Bit in Nth Binary String problem.

Statement

Given two positive integers n and k, a sequence of binary strings is generated using the following rules:

  • S1=“0”S_1 = \text{``0''}

  • Si=Si−1+“1”+reverse(invert(Si−1))S_i = S_{i-1} + \text{``1''} + \text{reverse}(\text{invert}(S_{i-1})) for i>1i > 1

Where:

  • ++ denotes string concatenation.

  • reverse(x) returns the string xx in reverse order.

  • invert(x) flips all bits in xx ("0" becomes "1" and "1" becomes "0").

Return the kthk^{\text{th}} bit of the string SnS_n, using 11-based indexing.

Constraints:

  • 1≤1 \leq n ≤20\leq 20

  • 1≤1 \leq k ≤2n−1\leq 2^{n} - 1

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Find Kth Bit in Nth Binary String

Try to solve the Find Kth Bit in Nth Binary String problem.

Statement

Given two positive integers n and k, a sequence of binary strings is generated using the following rules:

  • S1=“0”S_1 = \text{``0''}

  • Si=Si−1+“1”+reverse(invert(Si−1))S_i = S_{i-1} + \text{``1''} + \text{reverse}(\text{invert}(S_{i-1})) for i>1i > 1

Where:

  • ++ denotes string concatenation.

  • reverse(x) returns the string xx in reverse order.

  • invert(x) flips all bits in xx ("0" becomes "1" and "1" becomes "0").

Return the kthk^{\text{th}} bit of the string SnS_n, using 11-based indexing.

Constraints:

  • 1≤1 \leq n ≤20\leq 20

  • 1≤1 \leq k ≤2n−1\leq 2^{n} - 1