Different output for int and long on n = 50000

Resources & Problemsets
#1

CSES - missing number problem. given range for n is 2<n<10^5. using long long for n works for all test cases. but when using int for n, 5 test cases failed. I tested the n=50000 case.

Using long long

#include <iostream>
using namespace std;
int main() {
	freopen("test_input.txt", "r", stdin);
	long long sum = 0;
	long long n;
	cin >> n;
	long long tri = ((n+1)*n)/2;
	n--;
	while(n--){
		int x;
		cin >> x;
		sum += x;
	}
	cout << tri - sum << endl;
}

output >> 7626

Using int

#include <iostream>
using namespace std;
int main() {
	freopen("test_input.txt", "r", stdin);
	long long sum = 0;
	int n;
	cin >> n;
	long long tri = ((n+1)*n)/2;
	n--;
	while(n--){
		int x;
		cin >> x;
		sum += x;
	}
	cout << tri - sum << endl;
}

output >> -2147476022

I still don’t understand why n needs to be long long? As far as I know, In my code I didn’t overflow the n value. n value is updated only in while loop to take n inputs.

#2

When you do long long tri = ((n+1)*n)/2, it does not care about tri until it has already computed the right side. That is, it will compute ((n+1)*n)/2 first, then set whatever value it gets to tri. In the case where n is an int, when it multiplies n*(n+1), it will overflow because it is dealing in integers. Then it will set that incorrect overflow value to tri. If you want to keep n as an int, you can do

long long tri = (1ll*(n+1)*n)/2;

It will see the 1ll first, which is the integer 1 typecasted to a long long, so when it multiplies left to right, it will keep making sure that it is doing multiplication in long long because the left value will always be a long long.

1 Like
#3

Thanks. Now I understood.