You are given a sequence a1, a2, ..., aN. Find the smallest possible value of ai

Question

You are given a sequence a1, a2, ..., aN. Find the smallest possible value of ai + aj, where 1 <= i < j <= N. Input The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each description consists of a single integer N. The second line of each description contains N space separated integers - a1, a2, ..., aN respectively. Output For each test case, output a single line containing a single integer - the smallest possible sum for the corresponding test case. Constraints T = 105, N = 2 : 13 points. T = 105, 2 <= N <= 10 : 16 points. T = 1000, 2 <= N <= 100 : 31 points. T = 10, 2 <= N <= 105 : 40 points. 1 <= ai <= 106 Example Input:

1

4 5 1 3 4

Output: 4

Explanation / Answer

This is variant of sorting,can be solved using sorting

Problem : Given a sequence a1, a2, ..., aN. Find the smallest possible value of ai + aj, where 1 ? i < j ?N

Explanation

This problem was the easiest one in the set and it was intended to enable everybody to get some points.

How to get 13 points

Here you have only two integers a1 and a2, so the only possible sum will be a1+a2.

How to get 60 points

The constraints were designed in such a way that you can iterate through all the possible pairs (i, j), where 1 ? i < j ? N and check for every obtained sum, whether it's the minimal one.

How to get 100 points

The answer is basically the sum of the minimal and the second-minimal element in the array. So you can simply iterate through all the numbers, keeping track of the minimal and the second-minimal number. Or if your programming language has built-in sorting, you can act even simpler, because after the sorting of the array in increasing order, the required minimal and the second-minimal will be the first and the second elements of the sorted array.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.