Dividing Stamps | CodeChef

1

The question link is

Whenever I am initializing the variables (to store the sum of number of stamps and the sum of first N natural numbers) as long long, the verdict is WA. If I change to int, the verdict is AC.
The link of WA verdict:-
https://www.codechef.com/viewsolution/31763380
The link of AC verdict:-
https://www.codechef.com/viewsolution/31763291

Can anyone explain it??

1 Like
2

Your AC code fails on this test case

5
1000000000 1000000000 1000000000 1000000000 294967311

Tell me if you weren’t able to figure why it happens, and what is the correct answer.

3

Actually, I have initiated both sums as INT, but sum of these numbers cant be stored in INT.

4

When it overflows it almost always gives the same answer, so the chance of getting a test wrong is \approx 10^{-10}.
In the WA answer write
long long int m=(long long)n*(n+1)/2;
It overflows before it goes in m.

5

I didn’t get the first line. Can you elaborate?

6

Overflow basically calculates the answer mod 2^{32}. The chance of 2 different numbers being equal mod 2^{32} is very low, that’s why your second solution got AC.

7

Got it. Thank you