ADVITIYA3 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: ladchat
Tester: apoorv_me
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

There are N cookie jars, with the i-th containing A_i cookies.
A mother wants to distribute cookies from one of the jars to her K children, such that:

  • Each child receives at least one cookie; and
  • Each child receives an equal number of cookies.

What’s the minimum number of cookies remaining in a jar after distribution?

EXPLANATION:

Suppose cookies from the i-th jar are to be distributed. Then,

  • A_i \geq K should hold, so that it’s even possible for each child to receive a cookie.
  • The number of remaining cookies should be minimized while ensuring that each child receives an equal number of cookies.
    This means each child will receive \left\lfloor \frac{A_i}{K} \right\rfloor cookies; and more importantly, the number of remaining cookies is A_i \bmod K, i.e, the remainder when A_i is divided by K.

So, the final answer is the minimum value of (A_i\bmod K) across all indices i such that A_i\geq K.
If no such index exists, the answer is -1 instead.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    ans = -1
    for x in a:
        if x < k: continue
        if ans == -1: ans = 10**9
        ans = min(ans, x%k)
    print(ans)