### kuldeep_devulapally's blog

By kuldeep_devulapally, history, 5 weeks ago,

# 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...

 » 5 weeks ago, # |   0 Auto comment: topic has been updated by kuldeep_devulapally (previous revision, new revision, compare).
 » 5 weeks ago, # |   0 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.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 4 weeks ago, # ^ |   0 Yes.
 » 4 weeks ago, # |   +3 The line It is guaranteed that the sum of n over all test cases does not exceed 10^5 is 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.
•  » » 4 weeks ago, # ^ |   +3 So basically the complexity will be O(T+n) not O(t*n)
•  » » » 4 weeks ago, # ^ |   0 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.
•  » » » » 4 weeks ago, # ^ |   0 Thank you for clarifying my doubt.
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by kuldeep_devulapally (previous revision, new revision, compare).