0329MediumStringRecursionSimulation

Crease Symbol After N Folding Passes

Tracked in this browser only

Trains the technique from

LeetCode 1545Find Kth Bit in Nth Binary String

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def crease_at(passes: int, slot: int) -> str:

Java

public char creaseAt(int passes, int slot)

The intended approach

Time O(n)Space O(1)

Each row is the previous row, then a lone 1, then a mirrored and swapped copy of the previous row. So compare the position with the middle of the current row: on the middle the answer is the lone symbol adjusted by the flips owed so far, past the middle the position reflects back into the previous row and one more flip is owed, and before the middle it carries over untouched. Repeat until the first row is reached.

Pythonentry point: crease_at

def crease_at(passes, slot):
    # Walk the position down one generation at a time. Landing past the middle
    # mirrors the position back into the previous pattern and owes one flip.
    # Time O(passes). Space O(1).
    flips = 0
    n = passes
    k = slot
    while n > 1:
        mid = 1 << (n - 1)
        if k == mid:
            return "0" if flips else "1"
        if k > mid:
            k = 2 * mid - k
            flips ^= 1
        n -= 1
    return "1" if flips else "0"

The obvious version

Materialise the whole row pass by pass and index into it.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_crease_at(passes, slot):
    pattern = "0"
    for _ in range(passes - 1):
        mirrored = "".join("1" if c == "0" else "0" for c in reversed(pattern))
        pattern = pattern + "1" + mirrored
    return pattern[slot - 1]

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in