Abstract / Summary

Given n and k find the kth bit in a string built by specific rules without solving it.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 74% (300k+ submissions).

Typical patterns to solve this problem:

• Recursion
• Simulation
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of locating the k-th character in the recursively defined binary string sₙ. The string construction follows the pattern s₁ = "0" and for each subsequent i the string sᵢ is built as sᵢ₋₁ + "1" + reverse(invert(sᵢ₋₁)). The algorithm exploits the deterministic structure of the string to compute the required bit without materializing the entire sequence, thereby keeping memory usage minimal and enabling fast queries even for large values of n.

Core Recursive Logic

The heart of the solution is the nested function deeper. It receives the current recursion depth n and the target position k (1-based) and returns the integer value of the bit at that location.

def deeper(n, k):
    if n == 1:
        return 0

    size = (2 ** n) - 1
    mid  = size // 2 + 1

    if k == mid:
        return 1
    if k <  mid:
        return deeper(n - 1, k)
    else:
        return deeper(n - 1, size - k + 1) ^ 1

The function first handles the base case n == 1, where the only character is '0'. For larger n it computes the total length of sₙ as 2ⁿ-1 and identifies the middle position mid. The middle character is always '1' (except for the base case already covered).

When k lies to the left of the middle, the problem reduces to the same query on the left half, which is exactly sₙ₋₁. The recursive call deeper(n - 1, k) handles this directly.

When k lies to the right of the middle, the algorithm maps the index to the symmetric position in the left half using size - k + 1. Because the right half is the bitwise complement of the reversed left half, the result of the recursive call is flipped with the XOR operation ^ 1. This single bitwise operation implements the inversion required by the construction rule.

The outer method simply converts the integer result to a string, matching the expected return type.

return str(deeper(n, k))

Edge Cases Addressed

The implementation explicitly treats the smallest possible input where n equals 1. In that scenario the string length is 1 and the only valid k is also 1. The early return if n == 1: return 0 guarantees correct output without further arithmetic.

The calculation of mid uses integer division and adds one, ensuring that the middle index is correctly identified for both odd and even lengths (though the length is always odd in this problem).

When k equals mid, the function returns 1 immediately, covering the case where the query targets the central '1'.

The right-side branch uses the expression size - k + 1 to compute the mirrored index. This expression works for any k greater than mid, including the extreme case where k is the last character of the string. The subsequent XOR with 1 flips the bit, handling the inversion required for the right half.

Implicit Performance Optimizations

The algorithm avoids constructing the full string sₙ, which would have exponential size. By working solely with integer arithmetic and recursion, it reduces memory consumption to O(n) stack frames, each holding a few scalar values.

The use of the power expression 2 ** n to compute the length is a constant-time arithmetic operation for the given n. Because the recursion depth decreases by one on each call, the total number of recursive invocations equals the distance from the original n down to the base case, which is at most n. This bounded recursion depth prevents runaway stack growth.

The XOR operation ^ 1 provides an O(1) bit flip, eliminating the need for conditional branching or string manipulation to achieve the complement.

By directly mapping a right-side index to its left-side counterpart (size - k + 1), the algorithm eliminates any need for reversing or copying data structures, thereby keeping the runtime tightly coupled to the recursion depth rather than the size of the string.

Overall, the solution leverages the mathematical properties of the recursively defined string to achieve a lean, direct computation that scales efficiently with the input parameters.

Imagine you have a long, magic string of numbers that grows like a secret pattern. To build this string, you start with a zero. To make the next one, you take what you had, add a one in the middle, and then take the first part, flip all the numbers so zeros become ones and ones become zeros, and put that at the end.

This code works like a detective trying to find one specific number at a certain spot in that long string. It uses a clever trick called recursion, which is like a box that calls a smaller version of itself to solve the problem.

First, the code calculates how big the current string is. If the spot we are looking for is exactly in the middle of the string, it knows the answer is a one because that is how the pattern is built. If the spot is in the first half, the code just starts over with a smaller version of the string to find the same spot. If the spot is in the second half, it does something special. It looks at the mirror image spot on the other side and magically flips the result, changing a zero to a one or a one to a zero. It keeps doing this, folding the problem in half over and over until it reaches the very beginning where there is only a single zero, which makes finding the answer very simple.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java					TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java	JS		Go	Rust	TS
	Progiez	C++	Python	Java
github	black-shadows	C++
	charles-wangkai			Java
	everthis				JS
	FelixFan1122			Java
	fsq	C++
	JoshCrozier				JS
	keineahnung2345	C++
	lkwq007		Python
	suxrobGM					C#
	trung-hn		Python
	varunu28			Java
	wisdompeak	C++
	withaarzoo	C++
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
FelixFan1122	Java
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++
withaarzoo	C++
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality