0658MediumMathBit ManipulationRecursion

Symbol in the Woven Row

Tracked in this browser only

Trains the technique from

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 loom builds a pattern one row at a time. Row 1 is a single symbol, 0. Every later row is woven from the row above it by replacing each of its symbols, left to right, with a pair: a 0 becomes 0 then 1, and a 1 becomes 1 then 0.

So row 2 reads 01, row 3 reads 0110, and in general row r holds 2^(r - 1) symbols.

Given a row number row and a position spot, counting positions from 1 at the left, return the symbol standing at that position of that row. The row can be far too wide to write out, so do not weave it symbol by symbol.

Examples

Example 1

Input: row = 3, spot = 3
Output: 1

Row 3 reads 0110, and its third symbol is 1.

Example 2

Input: row = 4, spot = 5
Output: 1

Row 4 reads 01101001, and its fifth symbol is 1.

Example 3

Input: row = 5, spot = 16
Output: 0

Row 5 holds 16 symbols and reads 0110100110010110, so the symbol at the far right is 0.

Constraints

1 <= row <= 30
1 <= spot <= 2^(row - 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 woven_symbol(row: int, spot: int) -> int:

Java

public int wovenSymbol(int row, int spot)

The intended approach

Time O(log spot): one iteration per bit of spot - 1.Space O(1).

Each symbol of a row expands into a pair whose first half copies its parent and whose second half is the parent flipped. Stepping from the wanted position back up the rows halves the position each time, and the low bit of the current position minus one says whether that step landed in the flipped half. Since row 1 holds a `0`, the answer is simply the parity of the number of 1 bits in `spot - 1`, which one pass over those bits computes and which never touches the row number.

Pythonentry point: woven_symbol

def woven_symbol(row, spot):
    # Row r holds 2^(r-1) symbols. Reading spot - 1 in binary, every 1 bit marks a
    # step where the wanted symbol sat in the second half of its parent block and
    # therefore came out flipped. So the answer is the parity of those 1 bits.
    # O(log spot) time, O(1) space.
    offset = spot - 1
    flips = 0
    while offset:
        flips ^= offset & 1
        offset >>= 1
    return flips

The obvious version

Halve the row instead of the position. The first half of row `r` is exactly row `r - 1`, and the second half is row `r - 1` with every symbol flipped, so recurse into whichever half holds the position, flipping the result when it is the second.

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_woven_symbol(row, spot):
    if row == 1:
        return 0
    half = 1 << (row - 2)
    if spot <= half:
        return bf_woven_symbol(row - 1, spot)
    return 1 - bf_woven_symbol(row - 1, spot - half)

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 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