Why does it output -294967296

Question

So in leetcode 4 sum there is a test case [1000000000,1000000000,1000000000,1000000000] and for some reason the addition of these is equal to -294967296 and i do not understand how exactly this works i assumed it was because the actual answer is larger than max val of an int but i tried that and it just threw an error instead so why does that not happen here

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        if(target>Integer.MAX_VALUE||target<Integer.MIN_VALUE){
            return new ArrayList();
        }
        int lb =0;
        int ub  = nums.length-1;
        int sum = 0;
        HashSet<List<Integer>> ans = new HashSet();
        Arrays.sort(nums);
        for(int i = 0;i<nums.length;i++){

            for(int j = i+1;j<nums.length;j++){
                lb = j+1;
                ub = nums.length-1;
                while(lb<ub){

                    sum = nums[i]+nums[j]+nums[lb]+nums[ub];
                    if(sum==-294967296){
                        System.out.println(sum);
                        System.out.println(nums[i]);
                        System.out.println(nums[j]);
                        System.out.println(nums[lb]);
                        System.out.println(nums[ub]);
                    }
                    if(sum==target){
                        ans.add(Arrays.asList(nums[i],nums[j],nums[lb],nums[ub]));
                        lb++;
                        ub--;
                    }else if(sum<target){
                        lb++;
                    }else{
                        ub--;
                    }

                }
            }
        }
        List<List<Integer>> ret = new ArrayList(ans);
        return ret;
    }
}

this is the code i wrote and i dont think there is an issue here

Answer 1

First of all...

if(target>Integer.MAX_VALUE||target<Integer.MIN_VALUE){
    return new ArrayList();
}

This if statement will never trigger because an int by definition cannot be smaller than Integer.MIN_VALUE or larger than Integer.MAX_VALUE. In other words, target > Integer.MAX_VALUE || target < Integer.MIN_VALUE will always evaluate to false.

The maximum value an int variable can hold is 2^31 - 1, or 2,147,483,647. Your sum is exactly 4 billion which causes your integer variable to overflow.

You really should use long variables to operate on values of this magnitude.

P.S. What does integer overflow mean? byte, short, int and long numbers in Java are stored using the 2's complement system. The first bit of the value stores the sign. If it's equal to 0, the number is positive; if it's 1, the number is negative. Thus the largest positive value an int can hold is 01111111111111111111111111111111 in binary. This number happens to be 2,147,483,647 in decimal. If you add 1 to it, it becomes 10000000000000000000000000000000, which is -2,147,483,648 in decimal (it's negative because the first bit is now 1).