Zero Remainder Array (Codeforces 1374D)
Tags: Math, two pointers

You are given an array $$$a$$$ consisting of $$$n$$$ positive integers.Initially, you have an integer $$$x = 0$$$. During one move, you can do one of the following two operations:  Choose exactly one $$$i$$$ from $$$1$$$ to $$$n$$$ and increase $$$a_i$$$ by $$$x$$$ ($$$a_i := a_i + x$$$), then increase $$$x$$$ by $$$1$$$ ($$$x := x + 1$$$).  Just increase $$$x$$$ by $$$1$$$ ($$$x := x + 1$$$). The first operation can be applied no more than once to each $$$i$$$ from $$$1$$$ to $$$n$$$.Your task is to find the minimum number of moves required to obtain such an array that each its element is divisible by $$$k$$$ (the value $$$k$$$ is given).You have to answer $$$t$$$ independent test cases. 

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.The first line of the test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5; 1 \le k \le 10^9$$$) — the length of $$$a$$$ and the required divisior. The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.It is guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

Output: For each test case, print the answer — the minimum number of moves required to obtain such an array that each its element is divisible by $$$k$$$.

Note: Consider the first test case of the example:  $$$x=0$$$, $$$a = [1, 2, 1, 3]$$$. Just increase $$$x$$$;  $$$x=1$$$, $$$a = [1, 2, 1, 3]$$$. Add $$$x$$$ to the second element and increase $$$x$$$;  $$$x=2$$$, $$$a = [1, 3, 1, 3]$$$. Add $$$x$$$ to the third element and increase $$$x$$$;  $$$x=3$$$, $$$a = [1, 3, 3, 3]$$$. Add $$$x$$$ to the fourth element and increase $$$x$$$;  $$$x=4$$$, $$$a = [1, 3, 3, 6]$$$. Just increase $$$x$$$;  $$$x=5$$$, $$$a = [1, 3, 3, 6]$$$. Add $$$x$$$ to the first element and increase $$$x$$$;  $$$x=6$$$, $$$a = [6, 3, 3, 6]$$$. We obtained the required array. Note that you can't add $$$x$$$ to the same element more than once.

Sample Inputs:
5
4 3
1 2 1 3
10 6
8 7 1 8 3 7 5 10 8 9
5 10
20 100 50 20 100500
10 25
24 24 24 24 24 24 24 24 24 24
8 8
1 2 3 4 5 6 7 8

Sample Outputs:
6
18
0
227
8

Solution (Python):
ans = []
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    temp = {}
    nums = list(map(int, input().split()))
    max_count = 0
    extra_count = 0
    for num in nums:
        res = num % k
        res = -res % k
        if res not in temp:
            temp[res] = 0
        temp[res] += 1
        if res:
            if temp[res] > max_count or (temp[res] == max_count and res >= extra_count):
                max_count = temp[res]
                extra_count = res + 1
    x = (max_count - 1) * k + extra_count if max_count >= 1 else extra_count
    ans.append(str(x))
print('\n'.join(ans))

Solution (Python):
from collections import defaultdict

def solve():
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    rem_counts = defaultdict(int)
    max_moves = 0
    for num in a:
        rem = num % k
        if rem != 0:
            rem_counts[rem] += 1
            max_moves = max(max_moves, rem_counts[rem] * k - rem)
    if max_moves > 0:
        max_moves += 1
    print(max_moves)
T = int(input())
for t in range(T):
    solve()

Solution (Python):
from sys import stdin, stdout
import bisect

def st():
    return list(stdin.readline())

def inp():
    return int(stdin.readline())

def li():
    return list(map(int, stdin.readline().split()))

def mp():
    return map(int, stdin.readline().split())

def pr(n):
    stdout.write(str(n) + '\n')

def soe(limit):
    l = [1] * (limit + 1)
    prime = []
    for i in range(2, limit + 1):
        if l[i]:
            for j in range(i * i, limit + 1, i):
                l[j] = 0
    for i in range(2, limit + 1):
        if l[i]:
            prime.append(i)
    return prime

def segsoe(low, high):
    limit = int(high ** 0.5) + 1
    prime = soe(limit)
    n = high - low + 1
    l = [0] * (n + 1)
    for i in range(len(prime)):
        lowlimit = low // prime[i] * prime[i]
        if lowlimit < low:
            lowlimit += prime[i]
        if lowlimit == prime[i]:
            lowlimit += prime[i]
        for j in range(lowlimit, high + 1, prime[i]):
            l[j - low] = 1
    for i in range(low, high + 1):
        if not l[i - low]:
            if i != 1:
                print(i)

def power(a, n):
    r = 1
    while n:
        if n & 1:
            r = r * a
            n = n - 1
        else:
            a = a * a
            n = n >> 1
    return r

def solve():
    (n, k) = mp()
    l = li()
    d = {}
    x = []
    for i in l:
        a = i % k
        if a != 0:
            if a not in d:
                d[a] = 1
                x.append(k - a)
            else:
                x.append(k - a + k * d[a])
                d[a] += 1
    if len(x) > 0:
        pr(max(x) + 1)
    else:
        pr(0)
for _ in range(inp()):
    solve()