0992MediumMathBinary Search

Landing Exactly on the Marker

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 pointer sits at position 0 on a line of whole numbers. On move number k, counting the first move as one, the pointer travels exactly k places, and each move may be taken to the left or to the right.

Return the fewest moves that leave the pointer sitting exactly on marker.

Examples

Example 1

Input: marker = 4
Output: 3

One move right, then one left, then one right lands on the marker after three moves. Two moves cannot manage it, because they land on one place away from the start or three away, never four.

Example 2

Input: marker = -1
Output: 1

A single move to the left arrives straight away.

Example 3

Input: marker = 11
Output: 5

Four moves all rightward reach ten, one short, and no turning of them can shave a single place off, since turning a move around always shifts the finish by an even amount. Five moves rightward overshoot by four, and turning the second move around takes exactly four back.

Constraints

-10^9 <= marker <= 10^9
marker != 0

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 reach_number(marker: int) -> int:

Java

public int reachNumber(int marker)

The intended approach

Time O(sqrt(D)) for a distance of D, since the running total grows with the square of the move count.Space O(1).

Turning every move the other way mirrors the finishing position, so a marker and its opposite need the same number of moves. Work with how far the marker sits from the start and ignore its side. Taking every move rightwards after some number of moves lands on the running total of the move sizes. Turning one of those moves around pulls the finish back by twice that move's size, so from a fixed number of moves the reachable positions are the running total less any even amount that doubling a choice of move sizes can make. Two things follow. The running total has to be at least the distance, and the shortfall between them has to be even. Both together are also enough, because the sizes one through the move count can make every whole amount up to their own total, so half the shortfall is always available. So add move sizes until the running total reaches the distance, then keep adding until the shortfall turns even. That last part takes at most two more moves, because two moves in a row differ in size by one and so shift the shortfall's evenness on at least one of them.

Pythonentry point: reach_number

def reach_number(marker):
    want = marker if marker > 0 else -marker
    moves = 0
    total = 0
    while total < want or (total - want) % 2:
        moves += 1
        total += moves
    return moves

The obvious version

Hold every position the pointer could be sitting on. Start with the position it begins at, and for each move build the next collection by shifting every held position both ways by the move's size. Report the move count as soon as the marker turns up among them. Costs the collection, which grows with the square of the move count, rather than a single running total.

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_reach_number(marker):
    spots = set([0])
    moves = 0
    while marker not in spots:
        moves += 1
        nxt = set()
        for spot in spots:
            nxt.add(spot + moves)
            nxt.add(spot - moves)
        spots = nxt
    return moves

How this problem was checked

Reference solution executed against 15 test cases — 15 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