Difference Array Solution Codeforces

Table of Contents

Difference Array Solution Codeforces

You are given an array aa consisting of nn non-negative integers. It is guaranteed that aa is sorted from small to large.

For each operation, we generate a new array bi=ai+1aibi=ai+1−ai for 1i<n1≤i<n. Then we sort bb from small to large, replace aa with bb, and decrease nn by 11.

After performing n1n−1 operations, nn becomes 11. You need to output the only integer in array aa (that is to say, you need to output a1a1).

Input Difference Array Solution Codeforces

The input consists of multiple test cases. The first line contains a single integer tt (1t1041≤t≤104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains one integer nn (2n1052≤n≤105) — the length of the array aa.

The second line contains nn integers a1,a2,,ana1,a2,…,an (0a1an51050≤a1≤…≤an≤5⋅105) — the array aa.

It is guaranteed that the sum of nn over all test cases does not exceed 2.51052.5⋅105, and the sum of anan over all test cases does not exceed 51055⋅105.

Output Difference Array Solution Codeforces

For each test case, output the answer on a new line.

Example
input

Copy
5
3
1 10 100
4
4 8 9 13
5
0 0 0 8 13
6
2 4 8 16 32 64
7
0 0 0 0 0 0 0
output

Copy
81
3
1
2
0

Note Difference Array Solution Codeforces

To simplify the notes, let sort(a)sort⁡(a) denote the array you get by sorting aa from small to large.

In the first test case, a=[1,10,100]a=[1,10,100] at first. After the first operation, a=sort([101,10010])=[9,90]a=sort⁡([10−1,100−10])=[9,90]. After the second operation, a=sort([909])=[81]a=sort⁡([90−9])=[81].

In the second test case, a=[4,8,9,13]a=[4,8,9,13] at first. After the first operation, a=sort([84,98,139])=[1,4,4]a=sort⁡([8−4,9−8,13−9])=[1,4,4]. After the second operation, a=sort([41,44])=[0,3]a=sort⁡([4−1,4−4])=[0,3]. After the last operation, a=sort([30])=[3]a=sort⁡([3−0])=[3].

For Solution

Click Here

Leave a Comment