1408. The Nearest Multiple, With the Tie Settled

Given a and a positive b, print the multiple of b nearest to a. When a is exactly halfway between two multiples, print the larger one.

a may be negative. b is always positive.

a = 7, b = 5 -> 5 7 is 2 from 5 and 3 from 10 a = 8, b = 5 -> 10 a = -7, b = 5 -> -5 a = -8, b = 5 -> -10 a = 5, b = 10 -> 10 an exact tie, so the larger multiple wins a = -5, b = 10 -> 0 the tie is between -10 and 0, and 0 is larger

Read the last two lines carefully. "Larger" means larger as a number, not larger in magnitude, so a tie on the negative side rounds toward zero while a tie on the positive side rounds away from it. An unsettled tie rule would make this problem unanswerable, and that is why the statement pins it before any test asserts it.

## What most people try first

round((double) a / b) * b. Two things go wrong. A double has 53 bits of mantissa while |a| reaches 10^18, so the quotient is already inexact before rounding. And the library round breaks ties away from zero in C, C++ and Java, which gives -10 for a = -5, b = 10 rather than the 0 this problem asks for. So even with exact arithmetic the tie rule would be wrong.

The second attempt is ((a + b / 2) / b) * b. That is right for positive a and silently wrong for negative a, because the division truncates toward zero rather than flooring.

## Doubling turns the half into an integer

The multiple wanted is b * k where k is the integer nearest to a / b, ties going up. "Nearest with ties up" is exactly the floor of a half-shifted value:

k = floor(a/b + 1/2) = floor( (2a + b) / (2b) )

The doubling clears the fraction, so the whole computation is one floor division of integers, which is the primitive problem 1406 builds. The answer is then b * k.

## Why it is correct

Write a / b = k0 + f with k0 = floor(a/b) and 0 <= f < 1. The two candidate multiples are b * k0 and b * (k0 + 1), at distances f * b and (1 - f) * b. So k0 + 1 is at least as close exactly when 1 - f <= f, that is f >= 1/2, and in the tie case f = 1/2 the rule says to take k0 + 1, the larger. Meanwhile floor(a/b + 1/2) = floor(k0 + f + 1/2) is k0 when f < 1/2 and k0 + 1 when f >= 1/2. The two agree in every case, including the tie, and the argument never mentioned the sign of a, which is why no sign analysis appears in the code.

## The boundary that breaks a careless implementation

a = -5, b = 10 is the test the tie rule decides, and floor(-5/10 + 1/2) = floor(0) = 0, so the answer is 0. Any implementation that reaches for abs and restores the sign at the end gets -10 here, because it has symmetrised a rule that is deliberately not symmetric.

## Overflow

|a| reaches 10^18, so 2 * a reaches 2 * 10^18. That fits a signed 64-bit integer, whose limit is 9223372036854775807, and it is worth being precise about the smaller claim too: 2 * 10^9 also fits a signed 32-bit integer, whose limit is 2147483647. What does not fit 32 bits here is a itself, and a 32-bit build answers -1000000000 where the truth is 10^18. Since b <= 10^9, the denominator 2 * b reaches 2 * 10^9, and the product b * k is within b of a so it stays near 10^18. In JavaScript all of this is past 2^53, so BigInt is required.

## Cost

O(1) per query.

Constraints - `1 ≤ q ≤ 1000` - `-1000000000000000000 ≤ a ≤ 1000000000000000000` - `1 ≤ b ≤ 1000000000`