Skip to content

Integer Types & Overflow

In one sentence

Every integer type has a fixed number of bits, so it can only hold numbers in a fixed range. Step outside the range and the value silently wraps around: no error, just a wrong answer.

1. What problem does it solve?

Example — 1850E · Cardboard for Pictures (5-BinarySearch · C, rating 1100)

There are \(n\) square pictures with sides \(s_1, \dots, s_n\). Each is glued on a square of cardboard that sticks out by the same width \(w\) on every side, so picture \(i\) uses \((s_i + 2w)^2\) cardboard. In total exactly \(c\) cardboard was used. Find \(w\) (it is guaranteed to exist).

Limits: \(n \le 2\cdot10^5\), \(s_i \le 10^4\), \(c \le 10^{18}\).

Input                    Output
3 50
3 2 1                    1
1 100
6                        2

The used cardboard grows with \(w\), so we binary search on \(w\). The trap is arithmetic, not the idea. Try \(w = 5\cdot10^8\) with \(s_i = 10^4\):

\[ (s_i + 2w)^2 \approx (10^9)^2 = 10^{18}\ \text{per picture},\qquad n \cdot 10^{18} = 2\cdot10^{23}\ \text{in total.} \]

That is far beyond even long long, so the sum wraps around, can look small, and binary search walks the wrong way.

2. The math

2.1 Ranges

A type with \(w\) bits has \(2^w\) different bit patterns.

Type Bits Range Roughly
int 32 \(-2^{31} \dots 2^{31}-1\) \(\pm 2.1 \cdot 10^9\)
unsigned int 32 \(0 \dots 2^{32}-1\) \(4.3 \cdot 10^9\)
long long 64 \(-2^{63} \dots 2^{63}-1\) \(\pm 9.2 \cdot 10^{18}\)
unsigned long long / size_t 64 \(0 \dots 2^{64}-1\) \(1.8 \cdot 10^{19}\)

2.2 How to check a formula

Before writing a line, plug the largest allowed inputs into it:

Expression Worst case Fits in
\(a_i + a_j\) with \(a \le 10^9\) \(2\cdot10^9\) int barely; use ll
\(a_i \cdot a_j\) with \(a \le 10^9\) \(10^{18}\) ll
\(\sum a_i\) with \(n = 2\cdot10^5\), \(a \le 10^9\) \(2\cdot10^{14}\) ll
\(\sum (s_i+2w)^2\) in the example \(2\cdot10^{23}\) nothing: stop early

2.3 Stop early

We only need to know whether the total is more than \(c\). So add pictures one by one and return "too big" as soon as the running sum passes \(c\). Before that moment the sum is at most \(c \le 10^{18}\), and one more term is at most about \(10^{18}\), so the running sum never exceeds \(2\cdot10^{18} < 9.2\cdot10^{18}\).

The width itself is bounded too: one picture alone uses \((2w)^2 \le c \le 10^{18}\), so \(w \le 5 \cdot 10^8\) and every single term is at most \((10^4 + 10^9)^2 \approx 10^{18}\).

3. Lesson notes (29 March)

Notes

size() and Unsigned Integers in C++

For many STL containers, .size() returns an unsigned integer type.

That means its value can never be negative.

For example:

vector<int> a = {1, 2, 3};
cout << a.size() << '\n';

The result of a.size() is usually of type size_t, which is unsigned.

This can lead to surprising behavior:

vector<int> a = {1, 2, 3};
cout << a.size() - 5 << '\n';

This does not produce a negative number.

Instead, because the type is unsigned, it wraps around and becomes a very large number.

So when using .size(), be careful with subtraction and comparisons.

Common Unsigned Limits

C++ provides maximum values for unsigned integer types.

Examples:

  • UINT_MAX
  • ULLONG_MAX

These constants represent the largest value that can be stored in the corresponding unsigned type.

For example:

#include <climits>

cout << UINT_MAX << '\n';
cout << ULLONG_MAX << '\n';

Why Unsigned Overflow Looks Like Modulo

When an unsigned integer overflows, it wraps around.

This behavior is essentially arithmetic modulo \(2^w\), where w is the number of bits of the type.

For example:

  • an 8-bit unsigned integer works modulo \(2^8 = 256\)
  • a 32-bit unsigned integer works modulo \(2^{32}\)
  • a 64-bit unsigned integer works modulo \(2^{64}\)

So if an unsigned integer exceeds its maximum value, it wraps back to the beginning.

Example:

unsigned int x = UINT_MAX;
x = x + 1;
cout << x << '\n';

The result is 0.

That is because:

\[ UINT\_MAX + 1 \equiv 0 \pmod{2^{32}} \]

Similarly:

unsigned int x = 1;
x = x - 2;
cout << x << '\n';

This does not become -1.

Instead, it wraps around to a very large value.

Practical Advice

When writing competitive programming code:

  • be careful when subtracting from .size()
  • be careful when mixing signed and unsigned integers
  • prefer checking bounds explicitly before subtraction
  • if negative values are possible, use a signed type such as int or long long

Understanding integer types is important, because many bugs are not caused by the algorithm itself, but by incorrect assumptions about how the language stores numbers.

4. Worked solution — Cardboard for Pictures

Binary search for the largest \(w\) whose cardboard is at most \(c\) (the answer exists, so that \(w\) uses exactly \(c\)).

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

void solve() {
    int n;
    ll c;
    cin >> n >> c;
    vector<ll> s(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }

    // true if width w uses at most c cardboard; stop as soon as the sum passes c
    auto check = [&](ll w) -> bool {
        ll sum = 0;
        for (int i = 0; i < n; i++) {
            sum += (s[i] + 2 * w) * (s[i] + 2 * w);
            if (sum > c) {
                return false;
            }
        }
        return true;
    };

    ll l = 1, r = 500000000, ans = 1;
    while (l <= r) {
        ll mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T = 1;
    cin >> T;
    for (int i = 0; i < T; i++) {
        solve();
    }
    return 0;
}

5. Common mistakes

int × int stored into long long

ll x = a * b; with int a, b multiplies as int first and overflows before the assignment. Write (ll) a * b, or make a and b ll from the start.

for (int i = 0; i < v.size() - 1; i++) on an empty vector

v.size() - 1 is 0 - 1 in unsigned arithmetic, which is \(2^{64} - 1\). The loop runs off the end. Write i + 1 < v.size() instead.

Summing first, checking later

If a sum can be astronomically large but you only compare it with a limit, stop adding the moment it crosses the limit (§2.3).

1 << 40

1 is an int, so shifting by 31 or more is undefined. Write 1LL << 40.

6. Where overflow bit us in AIO

Problem The large quantity Fix
AIO 2026 · Prime Minister cost up to \(4 \cdot 10^{14}\) ll
AIO 2024 · Shopping Spree total price up to \(2 \cdot 10^9\) ll
AIO 2019 · Lollipops II sum of counts up to \(10^{10}\) ll
AIO 2022 · Spaceship Shuffle prefix sums up to \(10^{10}\) ll
Credits & licenses
  • §3 is the Notes part of the 29 March lesson, unchanged apart from heading levels.
  • Everything else (example, range tables, the early-stop bound, worked solution, mistakes) is ours.