Array operations

 Given an array 

A consisting of N

non-negative integers.

You need to perform the following operation (N−1)

times:

• Sort the array A

in ascending order.

Let M

be the current size of the array A. Replace the array A by [(A2−A1),(A3−A2),…,(AM−AM−1)]

• . Note that each time the operation is performed, the size of the array reduces by one.

Find the remaining element after (N−1)

operations.

Input Format

• The first line contains an integer T

denoting number of test cases. The T

test cases then follow.

The first line of each test case contains an integer N

- the size of the array.

The second line of each test case contains N

space-separated integers A1,A2,…,AN

• .

Output Format

For each test case, output single line: the remaining element after (N−1)

operations.

Constraints

• 1≤T≤105

1≤N≤105

0≤Ai≤1018

Sum of N

over all test cases does not exceed 2⋅105

• .

Sample Input 1

2
4
29 19 0 3
1
777

Sample Output 1

1
777

Explanation

• Test case 1: The operations look like:
  • Operation 1

: Sort the array. Now, A becomes [0,3,19,29]. Replace the array. Thus, A=[(3−0),(19−3),(29−19)]=[3,16,10]

.

Operation 2

: Sort the array. Now, A becomes [3,10,16]. Replace the array. Thus, A=[(10−3),(16−10)]=[7,6]

.

Operation 3

: Sort the array. Now, A becomes [6,7]. Replace the array. Thus, A=[(7−6)]=[1]

• • .

Thus, the remaining element after 3

operations is 1

.

• Test case 2: Since N=1

, you don't need to perform any operation. The remaining element after 0 operations is 777.

• Tweet
• Share
• Share
• Share
• Share

Related Post

• Adjacency Love An array is called lovely if the sum of product of each adjacent pair of elements is odd. Mor
• Permutation Xority You are given an integer NN. Construct a permutation AA of length NN 
• Count the Holidays A particular month has 3030 days, numbered from 11 to 3030.Day 
• Max BIT Sum Given two arrays A and B each of length N. Find the value ∑Ni=1∑Nj=1max(Ai⊕Bj,Ai&Bj)