Data Types and Overflow

Why this matters more in contests

In most programming, a value that exceeds the range of an int is a bug you eventually notice. In a contest, it is a bug that costs you the problem silently: your program runs, produces a number, and the number is wrong. There is no exception and no warning.

Overflow is one of the two or three most common reasons a correct algorithm scores zero. It is also completely avoidable by reading the constraints.

The ranges

Java integer types

The exact boundaries are available as constants, which is worth using instead of typing digits:

System.out.println(Integer.MAX_VALUE);  //  2147483647
System.out.println(Integer.MIN_VALUE);  // -2147483648
System.out.println(Long.MAX_VALUE);     //  9223372036854775807

What overflow looks like

When a computation exceeds the range, the result wraps around to the other end.

int big = Integer.MAX_VALUE;
System.out.println(big + 1);   // -2147483648, not 2147483648

The value silently becomes negative. Nothing is thrown.

int a = 100000;
int b = 100000;
long product = a * b;          // WRONG: 1410065408

long product = (long) a * b;   // correct: 10000000000

This pattern — an int multiplication assigned to a long — is worth learning to spot on sight. It appears constantly in problems that ask for a sum of products, an area, or a count of pairs.

Reading the constraints

The problem statement tells you which type you need. You have to do a small amount of arithmetic to find out.

Suppose a problem says: N ≤ 200,000, and each value is at most 10⁹. Print the sum of all values.

The largest possible sum is 200,000 × 10⁹ = 2 × 10¹⁴. That is well past the int limit of about 2 × 10⁹, so the accumulator must be a long.

int[] a = new int[n];          // values fit in int
// ...
long sum = 0;                  // the sum does not
for (int x : a) sum += x;

Storing the values as int and accumulating into a long is the normal shape. You rarely need a long array.

When long is not enough

If a result can exceed roughly 9 × 10¹⁸, you have three options, and the problem almost always intends one of them:

• The problem asks for the answer modulo some number, usually 10⁹+7. Then you reduce as you go and never exceed long. See Modular Arithmetic.
• The problem expects BigInteger, which has unlimited range but is much slower.
• Your approach is wrong and the intended solution never forms the huge value.

The third case is the most common. A quantity that overflows a long is usually a hint to reconsider the algorithm.

import java.math.BigInteger;

BigInteger a = BigInteger.valueOf(2).pow(100);
System.out.println(a);   // 1267650600228229401496703205376

Floating point

double holds about 15 to 16 significant decimal digits. It is the right type for geometry and for problems whose answer is genuinely a real number.

It is the wrong type for exact integer arithmetic. Two things go wrong:

System.out.println(0.1 + 0.2);           // 0.30000000000000004
System.out.println(0.1 + 0.2 == 0.3);    // false

Integer division and negative numbers

Java’s / truncates toward zero, and % takes the sign of the left operand. Both differ from the mathematical convention, and both cause bugs.

System.out.println(7 / 2);     //  3
System.out.println(-7 / 2);    // -3  (not -4)
System.out.println(-7 % 3);    // -1  (not 2)

When you need a non-negative remainder — common in modular arithmetic and in circular array indexing — normalize it:

static int mod(int a, int m) {
    return ((a % m) + m) % m;
}

For floor division on negatives, use Math.floorDiv and Math.floorMod, which behave the mathematical way:

System.out.println(Math.floorDiv(-7, 2));   // -4
System.out.println(Math.floorMod(-7, 3));   //  2

Next