I have seen this condition in some question like “sum of n over all the test cases <=10^6”… what does author wants to tell us with this condition…??(how can we use this condition in our solution ?)
In that example, 1 ≤ T ≤ 10^5, 1 ≤ n ≤ 10^5.
Without that constraint, you’d be looking at the worst case scenario, T=10^5, and in every case n=10^5. If the program were to run in O(n), it would take 10^10 iterations to solve the entire test, which is not feasible in under 2 seconds.
The condition serves as a clue: Because you have to process an overall input size of 10^6, you’re likely going to be looking for an O(n) solution.
2 Likes