Integer Overflow and Precision Tricks: Safe Arithmetic in Interviews

Algorithm/Topic Statement#

Integer overflow and floating point imprecision are silent killers in coding interviews. Whenever you multiply two values near 10 to the 9th in a 32-bit integer, the result wraps around and your algorithm starts producing nonsense. When you compare floats with equality, even arithmetically equivalent expressions disagree because of rounding. The defense is a toolkit of habits and idioms: pick wide enough integer types, use 128-bit intermediates or BigInt for products, avoid division when possible, replace equality with epsilon comparisons, and rely on integer square root and modular multiplication helpers when modulus times modulus exceeds the platform limit. Mastering these techniques is required for problems involving distances, factorials, modular combinatorics, or binary search on the answer.

Why This Topic Matters#

Most candidates who fail Google or Microsoft interviews on numeric problems do not stumble on the algorithm. They stumble on overflow. The interviewer asks for the median of a sorted matrix and the candidate writes lo plus hi divided by two without realizing that lo plus hi can overflow. The interviewer asks for a binary search on the answer for splitting an array and the candidate forgets that the upper bound is the array sum, which may exceed two billion. The candidate's logic is correct but the test case fails. By internalizing the overflow checklist, you eliminate an entire class of bugs that cost real points. Floating-point precision matters just as much. Computational geometry, probability problems, and any algorithm involving sqrt or trigonometry can return inconsistent comparisons if you do not use epsilon based logic or scaled integer arithmetic. These techniques also matter in production systems where billing, scientific computing, and cryptography all depend on understanding when ordinary math goes wrong.

The Core Insight (math intuition + proof sketch)#

A 32-bit signed integer holds values up to about 2.1 times 10 to the 9th. A 64-bit signed integer holds values up to about 9.2 times 10 to the 18th. The intuition behind safe arithmetic is to track the maximum possible value of every intermediate expression and choose a type at least one safety margin above. For multiplication of two values bounded by V, the product is bounded by V squared, so V squared must fit in your chosen type. For sums of n values each bounded by V, the sum is bounded by n times V. The proof of correctness for the binary search trick lo plus the difference divided by two is just algebra: lo plus hi minus lo over two equals lo plus hi over two minus lo over two, which equals the average without ever forming the sum that overflows.

For floating point, the IEEE 754 double has roughly 15 to 17 significant decimal digits. Operations like a plus b minus a do not always equal b because the addition step rounds. The proof technique here is interval analysis: track the absolute error after each operation, conclude that if your epsilon exceeds the accumulated error, comparisons remain reliable. Alternatively, scale to integers. If your inputs are coordinates with at most 9 digits, all squared distances fit in 64 bits, and you can do the entire computation without ever leaving exact arithmetic.

Visual Dry Run / Worked Example#

Consider computing the area of a triangle with vertices at coordinates near 10 to the 8th. The shoelace formula multiplies pairs of coordinates, and each product reaches 10 to the 16th. A 32-bit integer would overflow on the very first multiplication, while a 64-bit integer comfortably holds values up to about 9.2 times 10 to the 18th. This is the right type.

Now imagine a binary search on the answer for the classic split array problem with seven values each up to 10 to the 9th. The sum can reach 7 times 10 to the 9th, well past the 32-bit limit. Set lo to the maximum element and hi to the total sum, both stored in 64-bit integers. Compute mid as lo plus the difference of hi and lo divided by two to avoid forming a potentially overflowing sum. Iterate until lo equals hi.

For modular multiplication when the modulus is around 10 to the 12th, computing a times b modulo the modulus directly fails because a times b can reach 10 to the 24th. Cast to a 128-bit integer or use Python big integers, then reduce, and the answer is correct.

Solution / Implementation#

Python (no native overflow, but float traps remain)#

from fractions import Fraction
import math
 
def approx_equal(a, b, eps=1e-9):
    return abs(a - b) < eps
 
def is_perfect_square(n):
    if n < 0:
        return False
    r = math.isqrt(n)
    return r * r == n
 
def safe_avg(lo, hi):
    return lo + (hi - lo) // 2
 
def split_array(nums, k):
    def feasible(cap):
        parts, cur = 1, 0
        for v in nums:
            if v > cap:
                return False
            if cur + v > cap:
                parts += 1
                cur = 0
            cur += v
        return parts <= k
    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = safe_avg(lo, hi)
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

JavaScript (BigInt for safety, epsilon for floats)#

function approxEqual(a, b, eps = 1e-9) {
  return Math.abs(a - b) < eps;
}
 
function isqrtBig(n) {
  if (n < 0n) throw new Error('negative');
  if (n < 2n) return n;
  let x = n, y = (x + 1n) / 2n;
  while (y < x) { x = y; y = (x + n / x) / 2n; }
  return x;
}
 
function mulMod(a, b, mod) {
  return (BigInt(a) * BigInt(b)) % BigInt(mod);
}
 
function safeAvg(lo, hi) {
  return lo + Math.floor((hi - lo) / 2);
}

Time complexities depend on the surrounding algorithm. The overflow guards add only constant overhead. BigInt arithmetic in JavaScript is order log of the value per operation, so prefer it only for the final multiplication or modular reduction rather than wholesale.

Common Mistakes#

The classic mistake is writing lo plus hi divided by two in binary search. Always use lo plus the difference divided by two. Another bug is comparing floats with equality, especially after sqrt or trigonometric calls. Use a tolerance. People also forget that Java and C++ promote int times int to int, not long, so even if the result is assigned to a long the multiplication itself overflows. Cast at least one operand to long before multiplying. In Python, be careful with integer division of negative numbers, which floors rather than truncates and can surprise you when reducing modulo. Finally, when validating whether n is a perfect square, do not trust round of sqrt of n, because for very large n the float version loses precision; use the integer sqrt and verify by squaring.

Interview Tips#

When you see large constraints like values up to 10 to the 9th or array length up to 10 to the 6th, immediately ask whether the answer might exceed the integer range. Verbalize that you will use a 64-bit type or Python big integers. When binary searching, narrate the safe midpoint formula. If the interviewer asks about modular combinatorics with a non-prime modulus, mention CRT and 128-bit modular multiplication. For floating point, explain why epsilon comparisons are necessary and propose using integer arithmetic when possible. These small narrations show senior-level numeric judgment.

Follow-up Questions#

How would you implement multiplication of two 64-bit values modulo a 64-bit prime without using a 128-bit type? Could you describe Kahan summation and when you would use it? What goes wrong if you naively compute the determinant of a matrix using floating point, and how would Bareiss algorithm avoid the issue? Can you implement an integer cube root that handles all 64-bit inputs without overflow?

Key Takeaways#

• Always reason about the maximum value of every intermediate expression, then choose a type that comfortably contains it.
• Replace lo plus hi divided by two with lo plus the difference divided by two to prevent binary search overflow.
• Use 128-bit integers, BigInt, or Python big integers for products that approach the platform limit.
• Compare floats with an epsilon and prefer integer arithmetic on coordinates when the data is bounded.
• Use language-provided integer square root for perfect square tests, never round of float sqrt.
• These habits separate senior engineers from juniors in numerical interviews and competitive programming.