Difference Array (Codeforces 1708D)
Tags: Others, 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):
from collections import defaultdict, OrderedDict
InputList = lambda Dtype: [Dtype(x) for x in input().split()]
import bisect

def solve():
    N = int(input())
    nums = InputList(int)
    n_zeros = bisect.bisect(nums, 0)
    nums = nums[n_zeros:]
    if not nums:
        return 0
    for _ in range(N - 1):
        diff = []
        if n_zeros:
            diff.append(nums[0])
            n_zeros -= 1
        for i in range(len(nums) - 1):
            cur = nums[i + 1] - nums[i]
            if cur:
                diff.append(cur)
            else:
                n_zeros += 1
        if not diff:
            return 0
        if len(diff) == 1:
            return diff[0]
        nums = sorted(diff)
if __name__ == '__main__':
    ReturnMode = True
    t = None
    if not t:
        t = int(input())
    if ReturnMode:
        for _ in range(t):
            ans = solve()
            if type(ans) == list:
                print(*ans)
            else:
                print(ans)
    else:
        for _ in range(t):
            solve()

Solution (Python):
import sys
import math
T = int(sys.stdin.readline())

def remove_zeros(A):
    zeros = 0
    for a in A:
        if a == 0:
            zeros += 1
        else:
            break
    return (zeros, A[zeros:])

def solve(A):
    (zeros, A) = remove_zeros(A)
    while True:
        if A == []:
            return 0
        if len(A) == 1:
            return A[0]
        new_A = [A[i + 1] - A[i] for i in range(len(A) - 1)]
        if zeros > 0:
            new_A = [A[0]] + new_A
            zeros -= 1
        new_A.sort()
        (new_zeros, A) = remove_zeros(new_A)
        zeros += new_zeros
for _ in range(T):
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    print(solve(A))

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()