0291MediumDynamic ProgrammingGreedyBit Manipulation

Gauge Calibration Presses

Tracked in this browser only

Trains the technique from

LeetCode 2571Minimum Operations to Reduce an Integer to 0

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 depth gauge reads offset millimetres away from true, and a technician zeroes it with a calibration dial. One press of the dial shifts the reading by a value that is a power of two - 1, 2, 4, 8, 16 and upward with no cap - and the same press decides whether that value is added to the reading or taken off it.

Presses may overshoot: the reading is free to rise past where it started or fall past zero on the way, and nothing forces the reading to shrink at every press. Calibration is finished the moment the reading is exactly 0.

Given offset, return the fewest presses that bring the reading to 0.

Examples

Example 1

Input: offset = 23
Output: 3

Adding 1 takes the reading to 24, taking off 8 leaves 16, and taking off 16 lands on 0. Each shift is a power of two, so that is three presses.

Example 2

Input: offset = 6
Output: 2

Taking off 2 leaves 4 and taking off 4 lands on 0, so two presses are enough.

Constraints

1 <= offset <= 10^5

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 gauge_presses(offset: int) -> int:

Java

public int gaugePresses(int offset)

The intended approach

Time O(log offset)Space O(1)

Because the presses commute, the task is to write the offset as a signed sum of powers of two with the fewest terms. Walk the binary form from the low end: shift past a clear bit for free, spend one press to clear a lone set bit, and spend one press to add 1 when the bit above is also set, which carries a whole run of ones upward as a single higher power.

Pythonentry point: gauge_presses

def gauge_presses(offset):
    # Bringing the offset to zero is the same as writing it as a signed sum of
    # powers of two with as few terms as possible, because the presses may be
    # applied in any order.  Scan upward from the low bit: an isolated set bit is
    # cleared by one downward press, while a set bit whose neighbour above is also
    # set is carried upward by one upward press instead.
    # O(log offset) time, O(1) space.
    presses = 0
    while offset:
        if offset & 1:
            if (offset >> 1) & 1:
                offset += 1
            else:
                offset -= 1
            presses += 1
        else:
            offset >>= 1
    return presses

The obvious version

Breadth-first search over reading values, expanding each value by adding and subtracting every power of two that stays inside a bound twice the starting magnitude, and report the depth at which 0 first appears.

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

from collections import deque


def bf_gauge_presses(offset):
    limit = 1 << (offset.bit_length() + 1)
    powers = [1 << i for i in range(offset.bit_length() + 2)]
    seen = {offset}
    queue = deque([(offset, 0)])
    while queue:
        cur, d = queue.popleft()
        if cur == 0:
            return d
        for p in powers:
            for nxt in (cur + p, cur - p):
                if -limit <= nxt <= limit and nxt not in seen:
                    seen.add(nxt)
                    queue.append((nxt, d + 1))
    return -1

How this problem was checked

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