โ† Amazon questions

Find Kth Bit in Infinite String

Filed under Amazon

Free read 2 of 3

The sequence length doubles each step. The middle element is always '1'. The left half is S_{n-1}, the right is the inverted reverse of S_{n-1}.

The question

Given an infinite string S generated by S_0 = '0', S_n = S_{n-1} + '1' + invert(reverse(S_{n-1})), find the k-th bit (0-indexed).

Constraints

  • k can be very large (up to 10^18).
  • Must avoid generating the string explicitly.
  • Time complexity: O(log k).

Examples

Input
k=2
Output
1
Why
S_0='0', S_1='011', S_2='0111001'. Index 2 is '1'.

Approach

  1. The sequence length doubles each step. The middle element is always '1'. The left half is S_{n-1}, the right is the inverted reverse of S_{n-1}.

Solution

O(n) time, O(n) space

Python
def findKthBit(n, k):
    if n == 1: return '0'
    mid = 1 << (n - 1)
    if k == mid: return '1'
    if k < mid: return findKthBit(n - 1, k)
    return '1' if findKthBit(n - 1, 2 * mid - k) == '0' else '0'

Tips

  • What they are testing: Tests with k values near powers of 2.
  • Common mistake: Trying to build the string or using recursion without considering the symmetry of the sequence.

Related Amazon questions

Collected from public candidate posts and coding forums. Updated Nov 2026.