Show problems as
Classic problem #1545MediumStringRecursionSimulation

Find Kth Bit in Nth Binary String

Real-world version: Crease Symbol After N Folding Passes
Tracked in this browser only
Read Find Kth Bit in Nth Binary String on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A strip of paper is folded over and over, and after each pass the machine prints the creases it can feel as a row of 0 and 1 symbols.

Write P(1) = "0". Every later pass builds its row from the previous one:

P(i) = P(i - 1) + "1" + swap(reverse(P(i - 1)))

Here reverse reads a row from back to front and swap turns each 0 into a 1 and each 1 into a 0. So P(2) is "011" and P(3) is "0111001", and in general P(n) holds 2^n - 1 symbols.

Given the pass number n and a 1-indexed position k, return the symbol standing at position k of P(n) as a string of length one.

Examples

Example 1

Input
n = 3, k = 5
Output
"0"

P(3) is `0111001`, and its fifth symbol is `0`.

Example 2

Input
n = 2, k = 3
Output
"1"

P(2) is `011` and the third symbol is `1`.

Example 3

Input
n = 4, k = 11
Output
"1"

P(4) is `011100110110001`, whose eleventh symbol is `1`.

Example 4

Input
n = 1, k = 1
Output
"0"

The very first row holds the single symbol `0`.

Constraints

  • 1 <= n <= 20
  • 1 <= k <= 2^n - 1

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def crease_at(passes: int, slot: int) -> str:
Java
public char creaseAt(int passes, int slot)

More on the same topics