Range of int

CodeChef-DSA-learners
1

In the question the range is 10^9 and no operations are being performed other than counting
But ‘int’ gives wrong answer.
After struggling a lot I changed the variables to ‘long int’ and it got accepted.

So is ‘int’ not sufficient for 10^9?

Code Here

2

You can easily find the limits of int:

#include <iostream>
#include <limits>

using namespace std;

int main()
{
    cout << "int min: " << std::numeric_limits<int>::min() << endl;
    cout << "int max: " << std::numeric_limits<int>::max() << endl;
}

and we see that, yes, they can easily accommodate the value 10^9.

However: what will the answer be if you have a testcase consisting of 100000 values - in particular, the values 100000,99999, \dots ,2,1 in descending order?

2 Likes
3

Thank you ver much!
Now i see, the limit is
1 + 2 + … n-1 = n*(n+1)/2-n. (count in worst case)
for n=10^5 this can well exceed 10^9.

2 Likes