Difference Array (Codeforces 1707B)
Tags: Implement, sortings

You are given an array $$$a$$$ consisting of $$$n$$$ non-negative integers. It is guaranteed that $$$a$$$ is sorted from small to large.For each operation, we generate a new array $$$b_i=a_{i+1}-a_{i}$$$ for $$$1 \le i < n$$$. Then we sort $$$b$$$ from small to large, replace $$$a$$$ with $$$b$$$, and decrease $$$n$$$ by $$$1$$$.After performing $$$n-1$$$ operations, $$$n$$$ becomes $$$1$$$. You need to output the only integer in array $$$a$$$ (that is to say, you need to output $$$a_1$$$).

Input: The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains one integer $$$n$$$ ($$$2\le n\le 10^5$$$) — the length of the array $$$a$$$.The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$0\le a_1\le \ldots\le a_n \le 5\cdot 10^5$$$) — the array $$$a$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2.5\cdot 10^5$$$, and the sum of $$$a_n$$$ over all test cases does not exceed $$$5\cdot 10^5$$$.

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

Note: To simplify the notes, let $$$\operatorname{sort}(a)$$$ denote the array you get by sorting $$$a$$$ from small to large.In the first test case, $$$a=[1,10,100]$$$ at first. After the first operation, $$$a=\operatorname{sort}([10-1,100-10])=[9,90]$$$. After the second operation, $$$a=\operatorname{sort}([90-9])=[81]$$$.In the second test case, $$$a=[4,8,9,13]$$$ at first. After the first operation, $$$a=\operatorname{sort}([8-4,9-8,13-9])=[1,4,4]$$$. After the second operation, $$$a=\operatorname{sort}([4-1,4-4])=[0,3]$$$. After the last operation, $$$a=\operatorname{sort}([3-0])=[3]$$$.

Sample Inputs:
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

Sample Outputs:
81
3
1
2
0

Solution (Python):
import bisect

def solve():
    n = int(input())
    g = list(map(int, input().split()))
    cnt = n - 1
    while cnt:
        cnt -= 1
        b = []
        for i in range(1, len(g)):
            b.append(g[i] - g[i - 1])
        b.sort()
        g = b[bisect.bisect(b, 0):]
        if len(g) <= cnt:
            g.insert(0, 0)
    print(g[0])
T = int(input())
for _ in range(T):
    solve()

Solution (Python):
import bisect

def solve():
    n = int(input())
    g = list(map(int, input().split()))
    cnt = n - 1
    while cnt:
        cnt -= 1
        b = []
        for i in range(1, len(g)):
            b.append(g[i] - g[i - 1])
        b.sort()
        g = b[bisect.bisect(b, 0):]
        if len(g) <= cnt:
            g.insert(0, 0)
    print(g[0])
T = int(input())
for _ in range(T):
    solve()

Solution (Python):
for i in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    a = [x for x in a if x]
    zeros = n - len(a)
    while zeros + len(a) > 1:
        b = []
        if zeros and len(a):
            b.append(a[0])
        if zeros:
            zeros -= 1
        for i in range(len(a) - 1):
            if a[i + 1] - a[i]:
                b.append(a[i + 1] - a[i])
            else:
                zeros += 1
        b.sort()
        a = b
    if zeros:
        print(0)
    else:
        print(a[0])