CODEWITHSUNDEEP
java
dgollahon
dgollahon

Reputation: 13

Using long in place of int causes extra cases of overflow in java. Why?

I wrote a solution for a Hackerrank challenge in which I sum a large amount of numbers into a total variable. When I used ints, I noticed I was overflowing in one test case, but all other test cases were outputting the correct answer. When I switched my total variable to a long to avoid overflowing, I started overflowing in two test cases (the same one as before and another one). Once I changed total, numToSell, and lastMax to longs, the program calculate the correct answer.

What would cause this to happen? I would expect that moving a variable from int to long should never cause overflow.

import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        while(T-->0)
        {
            int N = in.nextInt(); 
            int[] price = new int[N];

            for(int i = 0; i < N; ++i)
            {
                price[i] = in.nextInt();
            }

            int lastMax = price[N-1]; //works when this and numToSell are longs
            int numToSell = 0; 
            long total = 0; //if this is also an int, only overflows in one case in my samples
            for(int i  = N - 2; i >= 0; --i)
            {
                if(price[i] <= lastMax)
                {
                    ++numToSell;
                    total -= price[i];
                }
                else
                {
                    total += numToSell*lastMax;
                    lastMax = price[i];
                    numToSell = 0;
                }
            }
            total += numToSell*lastMax;
            System.out.println(total);

        }
    }
}

In the affected test case N is 39,384 and each number in the array is between 1 and 100000.

Upvotes: 1

Views: 79

Answers (3)

Ian
Ian

Reputation: 861

If total, numToSell, and lastMax, are all ints, there are some cases where things can cancel and give you the correct answer, accidentally. This doesn't necessarily happen if total is long but the other are ints.

Here's an example that walks through the loop.

prices = {2000001,2000000,2000000,2000000};
lastMax = 2000000;
numToSell = 0;
total = 0;
loop:
  iteration 1:
    numToSell = 1;
    total = -2000000  
  iteration 2:
    numToSell = 2;
    total = -4000000  // oh no, we underflowed if we are int, but not long!
  iteration 3:
    total = -4000000 + (2 * 2000000)  // let's take a deeper look at this below
    numToSell = 0;
    lastMax = 20000001
total += 0;

Let's take a look at this line: total = -4000000 + (2 * 2000000)

If total, numToSell, and lastMax are all ints, then total = 0. This is because total underflowed and (2 * 20000000) will overflow in the exact same way. So the two cancel out.

If they are all longs, then nothing overflows so total = -40000000 + (2 * 2000000) = 0.

If total is long, then total did not underflow when it was set to -4000000. But, (2 * 2000000) is an integer, which will overflow and become a negative number. So total will not be zero!

This is a case when having all ints works, having all longs works, but having a mix fails.

Upvotes: 0

anonymous
anonymous

Reputation: 1317

I am guessing if you just changed total to long and left numToSell and lastMax as int, then numToSell*lastMax would still overflow and giving you incorrect result which is then added onto total

Upvotes: 0

Elliott Frisch
Elliott Frisch

Reputation: 201537

Yes, because here

total += numToSell*lastMax;

if numToSell and lastMax are int that's integer multiplication. int * int = int. You then added the int to your long. When numToSell (or lastMax) is a long that particular multiplication instruction will work as you expect. And I note you perform that math in two places.

Upvotes: 2

Related Questions