K-th Symbol in Grammar
Real-world version: Symbol in the Woven RowThe statement here is our own: the same inputs, outputs and technique.
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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def woven_symbol(row: int, spot: int) -> int:public int wovenSymbol(int row, int spot)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 12 test cases: 12 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's