Find Kth Bit in Nth Binary String · Interview Problem

Leetcode

find-kth-bit-in-nth-binary-string

Medium

Strings

Recursion

Bit Manipulation

Find Kth Bit in Nth Binary String

Find the kth bit in the nth binary string generated by a specific recursive process.

Acceptance 80%

Problem Statement

Core description from the backend problem record.

Given two positive integers n and k, you are to find the kth bit in the nth binary string S_n. The sequence of binary strings is defined as follows:

Here, + denotes concatenation, reverse means reversing the string, and invert means changing each '0' to '1' and each '1' to '0'.

Your task is to return the character ('0' or '1') at position k (1-indexed) in the string S_n.

Two integers n and k.

A single character ('0' or '1') representing the kth bit of the nth binary string.

1 <= n <= 20 1 <= k <= length of S_n (which can be up to 2^n - 1)

Examples

Sample cases returned by the problem API.

Example 1

Input

n = 3, k = 1

Output

Explanation

S_3 = "0111001"; the 1st bit is '0'.

Example 2

Input

n = 4, k = 11

Output

Explanation

S_4 is "011100110110001"; the 11th bit is '1'.

Loading Preptin