We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Yeah, I wasn't very clear, sorry. In fact, count itself doesn't overflow, but the result of count*(count-1) does. Since count is an int, the multiplication is performed using int, and the result is an int, which only then is converted to long long and assigned to ans. By that time, it has already overflowed. Eg. if count is 10^5, count^2 is going to be 10^10, a value that is typically too large for a plain int. Always be careful when multiplication is involved - it is very easy to overflow, because in the general case, if you are multiplying 2 numbers that use n bits, the result can have 2n bits. For example, 16 uses 4 bits (1000). If you square it, you get 256 (100000000) - 9 bits in the result. In your case, assuming 32-bit ints and using 2's complement, you can use at most 31 bits to represent a positive value, and as such, any value of count that uses more than 16 bits will overflow. This means your code overflows every time count >= 2^16, which is 65536. So, as you see, it overflows even for relatively small values of count, that's why you failed so many tests. Hah... multiplication is so evil! Conclusion: always be careful with overflow when you're doing multiplication, it's very easy to blow it.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Sherlock and Pairs
You are viewing a single comment's thread. Return to all comments →
Yeah, I wasn't very clear, sorry. In fact,
count
itself doesn't overflow, but the result ofcount*(count-1)
does. Sincecount
is anint
, the multiplication is performed usingint
, and the result is anint
, which only then is converted tolong long
and assigned toans
. By that time, it has already overflowed. Eg. ifcount
is 10^5,count^2
is going to be10^10
, a value that is typically too large for a plainint
. Always be careful when multiplication is involved - it is very easy to overflow, because in the general case, if you are multiplying 2 numbers that usen
bits, the result can have2n
bits. For example, 16 uses 4 bits (1000
). If you square it, you get 256 (100000000
) - 9 bits in the result. In your case, assuming 32-bit ints and using 2's complement, you can use at most 31 bits to represent a positive value, and as such, any value ofcount
that uses more than 16 bits will overflow. This means your code overflows every timecount >= 2^16
, which is 65536. So, as you see, it overflows even for relatively small values ofcount
, that's why you failed so many tests. Hah... multiplication is so evil! Conclusion: always be careful with overflow when you're doing multiplication, it's very easy to blow it.