Integer Overflow

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import numpy as np
 
# Python's native int has no overflow (arbitrary precision)
large = 2**100
print(f"Python int: 2^100 = {large}")  # Works fine!
 
# But NumPy uses fixed-width types
int32_val = np.int32(2147483647)  # Maximum 32-bit signed
print(f"NumPy int32 max: {int32_val}")
 
# Adding 1 causes overflow (wraps around silently)
overflowed = np.int32(int32_val + 1)
print(f"Max + 1 = {overflowed}")  # Prints -2147483648 (wrapped to min!)
 
# This can corrupt calculations
a = np.int32(2000000000)
b = np.int32(1000000000)
c = np.int32(500000000)
 
# Is a + b > c? Mathematically yes (3 billion > 500 million)
# But with overflow...
sum_ab = a + b  # Overflows!
print(f"a + b = {sum_ab}")  # Prints -1294967296 (NEGATIVE!)
print(f"Is a + b > c? {sum_ab > c}")  # Prints False (WRONG!)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

# === BINARY SEARCH MIDPOINT ===
 
# DANGEROUS (in languages with fixed integers):
def binary_search_overflow_risk(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2  # If left + right > INT_MAX, overflow!
        # ...
 
# SAFE: Equivalent but avoids sum overflow
def binary_search_safe(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2  # Never overflows!
        # right - left is always non-negative and <= len(arr)
        # Adding to left is safe
        # ...
 
 
# === SUM AND AVERAGE ===
 
def average_buggy(arr):
    """Calculate average - vulnerable to sum overflow."""
    total = 0
    for x in arr:
        total += x  # In fixed-width: can overflow for large arrays or values
    return total / len(arr)
 
def average_safe(arr):
    """Calculate average incrementally to avoid sum overflow."""
    if not arr:
        return 0.0
    
    avg = 0.0
    for i, x in enumerate(arr):
        # Incrementally adjust average: new_avg = old_avg + (x - old_avg)/(i+1)
        avg += (x - avg) / (i + 1)
    return avg
    # This never sums more than two numbers at once!
 
 
# === FACTORIAL ===
 
def factorial_naive(n: int) -> int:
    """Factorial - overflows very quickly in fixed-width integers."""
    result = 1
    for i in range(2, n + 1):
        result *= i  # 13! exceeds 32-bit signed, 21! exceeds 64-bit signed
    return result
 
# For competition problems requiring modular arithmetic:
def factorial_modular(n: int, mod: int) -> int:
    """Factorial modulo 'mod' - prevents overflow."""
    result = 1
    for i in range(2, n + 1):
        result = (result * i) % mod  # Always stays < mod
    return result
 
 
# === COUNT PATHS IN GRID ===
 
def count_paths_overflow_risk(m: int, n: int) -> int:
    """Count paths in m×n grid - sum accumulation can overflow."""
    dp = [[1] * n for _ in range(m)]
    
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]  # Sum grows rapidly!
    
    return dp[m-1][n-1]
    # For a 100×100 grid, the number of paths is astronomical!
 
def count_paths_with_modulo(m: int, n: int, mod: int = 10**9 + 7) -> int:
    """Count paths modulo 'mod' - standard technique."""
    dp = [[1] * n for _ in range(m)]
    
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % mod  # Stays bounded
    
    return dp[m-1][n-1]
 
 
# === PRODUCT CALCULATIONS ===
 
def product_of_array(arr):
    """Product of array elements - explodes in size."""
    product = 1
    for x in arr:
        product *= x  # [2]*64 = 2^64, exceeds 64-bit signed!
    return product
 
def product_of_array_except_self_safe(arr):
    """
    Product of array except self, handling overflow with log.
    Uses logarithms to detect overflow before it happens.
    """
    import math
    
    # Sum of logs = log of product
    total_log = sum(math.log(abs(x)) if x != 0 else 0 for x in arr)
    negative_count = sum(1 for x in arr if x < 0)
    has_zero = any(x == 0 for x in arr)
    
    max_safe_log = math.log(2**62)  # Safe 64-bit threshold
    
    if total_log > max_safe_log:
        print("Warning: Product would overflow!")
    
    # Proceed with calculation or use modular arithmetic...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import java.lang.Math;
 
public class SafeArithmetic {
    public static void main(String[] args) {
        int a = Integer.MAX_VALUE;
        int b = 1;
        
        // UNSAFE: Silent overflow
        int unsafeSum = a + b;
        System.out.println("Unsafe sum: " + unsafeSum);  // -2147483648 (wrapped!)
        
        // SAFE: Throws ArithmeticException on overflow
        try {
            int safeSum = Math.addExact(a, b);
            System.out.println("Safe sum: " + safeSum);
        } catch (ArithmeticException e) {
            System.out.println("Overflow detected!");
        }
        
        // Other safe methods:
        // Math.subtractExact(a, b)
        // Math.multiplyExact(a, b)
        // Math.incrementExact(a)
        // Math.decrementExact(a)
        // Math.negateExact(a)
        
        // For computations that shouldn't throw, use long:
        long safeLong = (long) a + b;
        System.out.println("Long sum: " + safeLong);  // 2147483648 (correct!)
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

# === SCENARIO 1: Array Sum Comparisons ===
 
# Problem: Is sum of first half greater than sum of second half?
# BUGGY approach (in fixed-width languages):
def compare_halves_buggy(arr):
    n = len(arr)
    mid = n // 2
    sum1 = sum(arr[:mid])  # Can overflow
    sum2 = sum(arr[mid:])  # Can overflow
    return sum1 > sum2  # Comparison of overflowed values is meaningless!
 
# SAFE approach: Compute difference incrementally
def compare_halves_safe(arr):
    n = len(arr)
    mid = n // 2
    
    # Compute sum(first_half) - sum(second_half) directly
    # This stays bounded: max value is n * max_element
    difference = 0
    for i in range(mid):
        difference += arr[i]
    for i in range(mid, n):
        difference -= arr[i]
    
    return difference > 0
 
 
# === SCENARIO 2: Checking if Sum Equals Target ===
 
# Problem: Does a + b == target?
# BUGGY (in fixed-width languages):
def sum_equals_target_buggy(a, b, target):
    return a + b == target  # a + b might overflow!
 
# SAFE: Rearrange to avoid sum
def sum_equals_target_safe(a, b, target):
    return a == target - b  # Subtraction of bounded values is safe
    # (assuming target is a valid value in the range)
 
 
# === SCENARIO 3: Distance/Magnitude Calculations ===
 
# Problem: Euclidean distance between points
import math
 
# BUGGY: Squaring can overflow
def euclidean_distance_buggy(x1, y1, x2, y2):
    dx = x2 - x1
    dy = y2 - y1
    return math.sqrt(dx * dx + dy * dy)  # dx*dx can overflow!
 
# SAFE: Use math.hypot which handles this internally
def euclidean_distance_safe(x1, y1, x2, y2):
    return math.hypot(x2 - x1, y2 - y1)
    # math.hypot internally scales to avoid overflow/underflow
 
# For comparison only (no need for actual distance):
def is_closer(p1, p2, reference):
    """Is p1 closer to reference than p2?"""
    # Use squared distances to avoid sqrt
    # But be careful: squared distances can overflow even more easily!
    
    # For safety in fixed-width, compare component-wise if possible
    # Or use floating point for the comparison
    dx1, dy1 = float(p1[0] - reference[0]), float(p1[1] - reference[1])
    dx2, dy2 = float(p2[0] - reference[0]), float(p2[1] - reference[1])
    
    dist1_sq = dx1 * dx1 + dy1 * dy1
    dist2_sq = dx2 * dx2 + dy2 * dy2
    
    return dist1_sq < dist2_sq
 
 
# === SCENARIO 4: Running Product for Division Trick ===
 
# Problem: For each element, compute product of all OTHER elements
# (assuming no zeros for simplicity)
 
# BUGGY: Compute total product, then divide
def product_except_self_buggy(nums):
    total_product = 1
    for x in nums:
        total_product *= x  # OVERFLOW - product grows exponentially!
    
    return [total_product // x for x in nums]
 
# SAFE: Prefix and suffix products
def product_except_self_safe(nums):
    n = len(nums)
    result = [1] * n
    
    # Prefix products (left to right)
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
    
    # Suffix products (right to left)
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    
    return result
    # NOTE: Still can overflow if individual prefix/suffix products are huge
    # For true safety, use modular arithmetic if problem allows,
    # or use logarithms to check for overflow before computing
 
 
# === SCENARIO 5: Counting Problems with Large Answers ===
 
MOD = 10**9 + 7
 
# Problem: Count number of ways (e.g., paths, arrangements)
def count_arrangements(n: int) -> int:
    """Example: Count something that grows exponentially."""
    if n <= 1:
        return 1
    
    # dp[i] = number of ways for size i
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    
    for i in range(2, n + 1):
        # Sum over all previous states (hypothetical recurrence)
        for j in range(i):
            dp[i] = (dp[i] + dp[j]) % MOD  # Always keep bounded
    
    return dp[n]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

# === CONSTRAINT ANALYSIS EXAMPLE ===
 
def analyze_overflow_risk(problem_constraints: dict) -> None:
    """
    Analyze whether overflow is possible given problem constraints.
    
    Example constraints:
    {
        'n': 100000,           # Array size
        'max_value': 10**9,    # Maximum element value
        'operation': 'sum'     # What we're computing
    }
    """
    n = problem_constraints['n']
    max_val = problem_constraints['max_value']
    operation = problem_constraints['operation']
    
    INT32_MAX = 2**31 - 1
    INT64_MAX = 2**63 - 1
    
    if operation == 'sum':
        worst_case = n * max_val
        print(f"Worst-case sum: {n} × {max_val} = {worst_case:.2e}")
        print(f"  Fits in int32: {worst_case <= INT32_MAX}")
        print(f"  Fits in int64: {worst_case <= INT64_MAX}")
    
    elif operation == 'product':
        # Product of n elements each up to max_val
        worst_case = max_val ** n
        print(f"Worst-case product: {max_val}^{n}")
        print(f"  Log10: {n * math.log10(max_val):.1f} (vs int64 max: 18.9)")
        print(f"  WILL OVERFLOW for any fixed-width type!")
    
    elif operation == 'sum_of_squares':
        worst_case = n * (max_val ** 2)
        print(f"Worst-case sum of squares: {n} × ({max_val})² = {worst_case:.2e}")
        print(f"  Fits in int64: {worst_case <= INT64_MAX}")
    
    elif operation == 'pairwise_product_sum':
        # Sum of all pairwise products: n(n-1)/2 pairs, each up to max_val²
        num_pairs = n * (n - 1) // 2
        worst_case = num_pairs * (max_val ** 2)
        print(f"Worst-case pairwise product sum: {worst_case:.2e}")
        print(f"  Fits in int64: {worst_case <= INT64_MAX}")
 
# Example usage:
import math
 
# Typical competitive programming problem
analyze_overflow_risk({
    'n': 100000,
    'max_value': 10**9,
    'operation': 'sum'
})
# Output: Worst-case sum = 10^14, fits in int64 but NOT int32
 
analyze_overflow_risk({
    'n': 100000,
    'max_value': 10**9,
    'operation': 'sum_of_squares'
})
# Output: Worst-case = 10^23, exceeds even int64!
 
 
# === RUNTIME OVERFLOW DETECTION ===
 
def detect_overflow_in_sum(arr, expected_positive=True):
    """Check if sum computation likely overflowed."""
    # In Python, we can safely compute the true sum
    true_sum = sum(arr)
    
    # Simulate 64-bit overflow
    INT64_MAX = 2**63 - 1
    INT64_MIN = -(2**63)
    
    if true_sum > INT64_MAX:
        print(f"WARNING: Sum {true_sum:.2e} would overflow int64!")
        return True
    
    # Check for sign anomalies (would indicate overflow in fixed-width)
    if expected_positive and all(x >= 0 for x in arr):
        if true_sum < 0:  # In fixed-width, this means overflow
            print("WARNING: Positive sum became negative - overflow!")
            return True
    
    return False