You are given an array a of n positive integers and an integer x . You can do the…
- User
You are given an array a of n positive integers and an integer x . You can do the following two-step operation any (possibly zero) number of times:
Choose an index i (1≤i≤n ). Increase ai by x , in other words ai:=ai+x . Find the maximum value of the MEX of a if you perform the operations optimally.
The MEX (minimum excluded value) of an array is the smallest non-negative integer that is not in the array. For example:
The MEX of [2,2,1] is 0 because 0 is not in the array. The MEX of [3,1,0,1] is 2 because 0 and 1 are in the array but 2 is not. The MEX of [0,3,1,2] is 4 because 0 , 1 , 2 and 3 are in the array but 4 is not. Input Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤5000 ). The description of the test cases follows.
The first line of each test case contains two integers n and x (1≤n≤2⋅105 ; 1≤x≤109 ) — the length of the array and the integer to be used in the operation.
The second line of each test case contains n integers a1,a2,…,an (0≤ai≤109 ) — the given array.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105 .
Output For each test case, output a single integer: the maximum MEX of a if you perform the operations optimally.
- Assistant
To solve this problem, we need to figure out the maximum possible MEX (Minimum Excluded Value) of an array after optimally performing the allowed operations.
Understanding the Problem:
- Operation Allowed: Increase any element
a_iby multiples ofxany number of times. - Objective: Find the maximum MEX of the array after performing the operations.
Key Observations:
- Each element
a_ican be increased by any non-negative multiple ofx. - To maximize the MEX, we need to cover as many consecutive non-negative integers starting from
0as possible. - For a value
v, we can adjust anya_itovif:v ≥ a_i(v - a_i) % x == 0
Algorithm Steps:
-
Group Elements by Remainders:
- For each element
a_i, compute its remainder when divided byx(a_i % x). - Group elements with the same remainder.
- For each element
-
Sort Each Group:
- For each remainder group, sort the elements in increasing order.
-
Initialize Pointers for Each Remainder:
- For each remainder
r, maintain an indexpos[r]starting at0.
- For each remainder
-
Iterate Over Potential MEX Values:
- Start from
v = 0and incrementally try to assign elements to cover consecutive integers. - For each
v, compute its remainderr = v % x. - Check if there's an element in the group for remainder
rthat hasn't been assigned and is less than or equal tov.
- Start from
-
Assign Elements to Values:
- If an element is found (
a_i ≤ v), assign it tovand move the pointerpos[r]forward. - If no such element exists, we've found the MEX.
- If an element is found (
-
Output the MEX:
- The smallest
vwhere we can't assign an element is the MEX.
- The smallest
Implementation Details:
-
Data Structures:
- An array of lists to store elements grouped by their remainders.
- An array to keep track of positions (
pos[r]) in each remainder group.
-
Time Complexity:
- The algorithm runs in
O(n)time per test case, wherenis the number of elements in the array.
- The algorithm runs in
Code:
t = int(input()) for _ in range(t): n, x = map(int, input().split()) a_list = list(map(int, input().split())) from collections import defaultdict rem_groups = defaultdict(list) for ai in a_list: rem = ai % x rem_groups[rem].append(ai) # Sort the ai's within each remainder group for rem in rem_groups: rem_groups[rem].sort() # Initialize pointers for each remainder group pos = {} for rem in rem_groups: pos[rem] = 0 v = 0 while True: r = v % x if r not in rem_groups: # No ai's with this remainder, MEX is v break else: if pos[r] >= len(rem_groups[r]): # No more ai's in this remainder group break else: ai = rem_groups[r][pos[r]] if ai <= v: # We can use this ai to adjust to v pos[r] += 1 v += 1 else: # Cannot adjust ai to v break print(v) - Operation Allowed: Increase any element