Insert and Equalize (Codeforces 1902C)
Tags: Greedy, number theory

You are given an integer array $$$a_1, a_2, \dots, a_n$$$, all its elements are distinct.First, you are asked to insert one more integer $$$a_{n+1}$$$ into this array. $$$a_{n+1}$$$ should not be equal to any of $$$a_1, a_2, \dots, a_n$$$.Then, you will have to make all elements of the array equal. At the start, you choose a positive integer $$$x$$$ ($$$x > 0$$$). In one operation, you add $$$x$$$ to exactly one element of the array. Note that $$$x$$$ is the same for all operations.What's the smallest number of operations it can take you to make all elements equal, after you choose $$$a_{n+1}$$$ and $$$x$$$?

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$). All $$$a_i$$$ are distinct.The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output: For each testcase, print a single integer — the smallest number of operations it can take you to make all elements equal, after you choose integers $$$a_{n+1}$$$ and $$$x$$$.

Note: In the first testcase, you can choose $$$a_{n+1} = 4$$$, the array becomes $$$[1, 2, 3, 4]$$$. Then choose $$$x = 1$$$ and apply the operation $$$3$$$ times to the first element, $$$2$$$ times to the second element, $$$1$$$ time to the third element and $$$0$$$ times to the fourth element.In the second testcase, you can choose $$$a_{n+1} = 13, x = 4$$$.In the third testcase, you can choose $$$a_{n+1} = 9, x = 1$$$. Then apply the operation once to $$$a_{n+1}$$$.

Sample Inputs:
3
3
1 2 3
5
1 -19 17 -3 -15
1
10

Sample Outputs:
6
27
1

Solution (Python):
from math import gcd
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    g = 0
    for i in range(n - 1):
        g = gcd(g, a[i + 1] - a[i])
    g = max(g, 1)
    a.sort()
    j = n - 1
    res = a[-1]
    while True:
        while j >= 0 and a[j] > res:
            j -= 1
        if j < 0 or a[j] != res:
            break
        res -= g
    print((a[-1] * (n + 1) - (sum(a) + res)) // g)

Solution (Python):
import sys, os
ONLINE_JUDGE = not bool(os.environ.get('AURELIONY'))
if not ONLINE_JUDGE:
    import psutil, timeit
    process = psutil.Process(os.getpid())
    start = timeit.default_timer()
from io import BytesIO, IOBase
from math import *
import operator
from copy import *
from bisect import *
from collections import *
from itertools import *
from functools import *
from heapq import *
from array import array
from fractions import Fraction
from decimal import Decimal
from random import *
from string import *
import threading
choose = lambda n, r: reduce(operator.mul, range(n - r + 1, n + 1), 1) // factorial(r)

class DSU:

    def __init__(self, sz):
        self.parent = list(range(sz))
        self.sz = [1] * sz

    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def link(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a != b:
            self.parent[a] = b
            self.sz[b] += self.sz[a]

    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a != b:
            if self.sz[a] < self.sz[b]:
                self.parent[a] = b
                self.sz[b] += self.sz[a]
            else:
                self.parent[b] = a
                self.sz[a] += self.sz[b]

    def is_connected(self, a, b):
        return self.find(a) == self.find(b)

    def size(self, a):
        return self.sz[self.find(a)]

def sieve(maxprime):
    if maxprime == 1:
        return [0, 0]
    prime = array('b', [True]) * (maxprime + 1)
    prime[0] = False
    prime[1] = False
    p = 2
    prime[p] = True
    while p * p <= maxprime:
        if prime[p]:
            for e in range(p + p, maxprime + 1, p):
                prime[e] = False
        p += 1
    return prime

def segmented_sieve(l, r):
    n = int(sqrt(int(r + 1))) + 1
    prime = sieve(n)
    isPrime = array('b', [True]) * (r - l + 1)
    if l == 0:
        isPrime[0] = False
        isPrime[1] = False
    if l == 1:
        isPrime[0] = False
    for i in range(len(prime)):
        if not prime[i]:
            continue
        for j in range(max(i * i, (l + i - 1) // i * i), r + 1, i):
            isPrime[j - l] = False
    return isPrime
TIME_LIMIT = 1
MEMORY_LIMIT = 256
FAST_INPUT = FAST_OUTPUT = 1
MOD = 1000000007
sys.setrecursionlimit(100000)

def f(A, t, x):
    res = 0
    for e in A:
        res += (t - e) // x
    return res

def solve():
    n = gi()
    A = gis()
    if n == 1:
        print(1)
        return
    x = abs(A[1] - A[0])
    for i in range(2, n):
        x = gcd(x, abs(A[i] - A[0]))
    s = set(A)
    m = max(A)
    new_e = m + x
    for i in range(1, n + 1):
        curr = m - i * x
        if curr not in s:
            new_e = curr
            break
    A.append(new_e)
    t = max(A)
    print(f(A, t, x))

def main(t=1):
    t = gi()
    for i in range(t):
        solve()

def debug(state=0):
    if ONLINE_JUDGE:
        return
    end = timeit.default_timer()
    memory_usage = process.memory_info().rss / 1048576
    if end - start > TIME_LIMIT or memory_usage > MEMORY_LIMIT:
        if FAST_OUTPUT:
            sys.stdout.buffer.buffer.truncate(0)
            sys.stdout.buffer.buffer.seek(0)
        if end - start > TIME_LIMIT:
            print('TLE')
        if memory_usage > MEMORY_LIMIT:
            print('MLE')
        print(f'TIME: {round(end - start, 2)}s')
        print(f'MEMORY: {round(memory_usage)}MB')
        sys.stdout.flush()
        exit(0)
    if state == 1:
        sys.stdout.flush()
        print(f'TIME: {round(end - start, 2)}s')
        print(f'MEMORY: {round(memory_usage)}MB')

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.buffer_size = 8192
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, self.buffer_size))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, self.buffer_size))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
if FAST_INPUT:
    sys.stdin = IOWrapper(sys.stdin)
if FAST_OUTPUT:
    sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')
INF = 1061109567
INF64 = 4557430888798830399
EPS = sys.float_info.epsilon

def gs():
    return input()

def gi():
    return int(input())

def gis():
    return list(map(int, input().split()))

def gf():
    return float(input())

def gfs():
    return list(map(float, input().split()))

def impossible():
    (print(-1), exit(0))

def printarr(arr):
    print(*arr)
if __name__ == '__main__':
    threading.Thread(target=main).start()

Solution (Python):
from math import gcd
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    g = 0
    for i in range(n - 1):
        g = gcd(g, a[i + 1] - a[i])
    g = max(g, 1)
    a.sort()
    j = n - 1
    res = a[-1]
    while True:
        while j >= 0 and a[j] > res:
            j -= 1
        if j < 0 or a[j] != res:
            break
        res -= g
    print((a[-1] * (n + 1) - (sum(a) + res)) // g)