I have given two input description given for two different problems in codeforces.
Description-1:-
Each test consists of multiple test cases. The first line contains a single integer t (1≤t≤104) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer n (2≤n≤10^5) — the length of the array a.
The second line of each test case contains n integers a1,a2,…,an(0≤ai<n) — the elements of the array a.
It is guaranteed that the sum of n over all test cases does not exceed 10^5.
Description-2:-
The first line contains a single integer t (1≤t≤5⋅104) — the number of test cases.
The only line of each test case contains a single integer n (1≤n≤10^5).
Here my doubt is can we perform O(n) on both the questions or not and performing O(n) operations on 2nd one is getting me TLE. So how should i approach questions based on their complexity?
How important is this line in 1st input description:- It is guaranteed that the sum of n over all test cases does not exceed 10^5.
PS:- Thank You! my doubt has been clarified and what we can understand from this line is the sum of n over all testcases doesn't exceed 10^5 and we can perform O(N) operations on this problem within given time limit so the total numbers inputting will be T+N i.e 10^4+10^5 not T*N i.e 10^4*10^5 which can be done within 1 sec...
Auto comment: topic has been updated by kuldeep_devulapally (previous revision, new revision, compare).
I assume you meant to write $$$10^{5}$$$ instead of $$$105$$$, that line is extremely important because then there could be $$$5\cdot10^{4}\cdot10^5 = 5\cdot10^{9}$$$ integers in the input. Reading that under a few seconds is impossible.
so can we use O(n) complexity for that problem? and does that mean the input size is not gonna be 5.10^9 right.
Yes.
The line
It is guaranteed that the sum of n over all test cases does not exceed 10^5is a very important line. The line means that there are T integers $$$n_1, n_2, ..., n_T$$$, $$$n_i$$$ being the $$$n$$$ in i-th test case and $$$n_1 + n_2 + ... + n_T <= 10^5$$$. Now, inputting T integers $$$n_1, n_2, ..., n_T$$$ is easy. But, there are $$$n_i$$$ more numbers in the i-th test case but as we know that sum of all $$$n_i <= 10^5$$$, then we are just inputting at most $$$T + 10^5$$$ numbers, which can be easily done in 1 second.So basically the complexity will be O(T+n) not O(t*n)
Yeah. That line just tells you that you don't need to take test cases into consideration, so you can just solve for T=1 and N having maximal value.
Thank you for clarifying my doubt.
Auto comment: topic has been updated by kuldeep_devulapally (previous revision, new revision, compare).