 # Sum of N doesn't exceed 10^5 for all test cases

Many questions contain a condition similar to this:

Sum of N doesn’t exceed 10^5 for all test cases.

I can never understand the significance of this line, is there any kind of optimization/catch that the author is usually suggesting here most of the times? Can anyone explain the significance of such a condition in a question? Preferably with an example problem would be better.

3 Likes

purohit

@anon42667337, See sum of N doesn’t exceed 10^5 means,

Let’s say for example, for a problem,
CASE 1: if T = 100 and N = 10^5, then, if you iterate over the 10^5 elements, then in the worst case, you will end up doing T * N which is 100*10^5 = 10^7 iterations, which can run smoothly in less than or equal to 1 sec.

Because for ex, in java, 10^7 iterations will run in 1 sec.

Now,
CASE 2: IF T = 10^5 AND N = 10^5, You can’t even linearly iterate over all the elements to find something, because T*N will be 10^10, Hence, they do tell, the sum of N over all test cases will not exceed 10^5 something like that, such that there woudn’t be any TLE, but your solution will be tested against T test cases in a single go.

6 Likes