Find Kth Bit in Infinite String
Filed under Amazon
Free read 2 of 3The 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
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}.
If k is the middle index, return 1. If k < middle, recurse on S_{n-1}. If k > middle, recurse on the inverted reverse, flipping the result.
Find the smallest power of 2 greater than k to determine the current sequence length and work backwards.
Solution
O(n) time, O(n) space
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.