1497. Check If Array Pairs Are Divisible by k
Problem Description
The problem presents an array of integers arr
with an even number of elements n
and an integer k
. The task is to determine whether arr
can be partitioned into n/2
pairs, where the sum of the integers in each pair is divisible by k
. If such a partitioning is possible, the function should return true
; otherwise, it should return false
.
Intuition
The solution is built on the property of divisibility by an integer k
. If two numbers a
and b
have a sum that is divisible by k
, it means that (a + b) % k == 0
. In other words, the remainder when a + b
is divided by k
is 0.
For any integer x
, x % k
will give a remainder in the range [0, k-1]
. If x % k
is 0
, then x
is divisible by k
. To make a pair with a sum divisible by k
, each number x
in the array that has a non-zero remainder x % k
requires a corresponding number y
such that (x + y) % k == 0
.
We can think of the remainders as forming pairs themselves. For a non-zero remainder i
, there must be an equal number of elements with remainder k - i
.
To arrive at the solution, we use a counter to track the frequency of each remainder in the array. We then check two conditions:
- The count of elements with a remainder of
0
must be even because they can only be paired with other elements with a remainder of0
. - For each non-zero remainder
i
, there should be an equal count of elements with remainderi
andk - i
.
If both these conditions are met, the array can be rearranged into n/2
pairs, where the sum of each pair is divisible by k
.
Solution Approach
The implementation of the solution involves using the Counter
class from Python's collections
module to efficiently count the occurrences of each remainder when elements of the array are divided by k
. The Counter
object will map each unique remainder to the number of times it appears in the array.
Here's a step-by-step walkthrough of the solution:
- Calculate the remainder of each element in the array when divided by
k
. This is done using a list comprehension:[x % k for x in arr]
. - Feed this list of remainders into
Counter
to get the frequency count of each remainder:Counter(x % k for x in arr)
. - Verify the first condition for elements with zero remainders:
cnt[0] % 2 == 0
. This checks if the count of elements that are exactly divisible byk
is even. These elements can only be paired with themselves, so an odd count would make it impossible to form pairs where the sum is divisible byk
.
- Verify the second condition for elements with non-zero remainders:
- Loop through the range from 1 to
k - 1
and for eachi
, check if the count of elements with a remainder ofi
is equal to the count of elements with a remainder ofk - i
. - This check is performed by the list comprehension:
all(cnt[i] == cnt[k - i] for i in range(1, k))
. - The
all
function ensures that this condition must hold true for all remainders in the specified range for the function to returntrue
.
- Loop through the range from 1 to
The use of the Counter
and the all
function makes the algorithm efficient and concise. The time complexity of this algorithm is primarily dependent on the time it takes to traverse the array and calculate the remainders, which is ( O(n) ), and the time to check the pair frequencies, which is ( O(k) ). This makes the overall time complexity ( O(n + k) ).
Here's the relevant snippet from the Python solution for reference:
class Solution:
def canArrange(self, arr: List[int], k: int) -> bool:
cnt = Counter(x % k for x in arr)
return cnt[0] % 2 == 0 and all(cnt[i] == cnt[k - i] for i in range(1, k))
By adhering to these steps, the algorithm efficiently solves the problem while respecting the constraints of even length arrays and the divisibility requirement.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example:
Suppose we have an array arr = [2, 4, 1, 5]
and an integer k = 3
. We need to check if we can partition this array into pairs such that the sum of each pair is divisible by k
. Since there are 4
elements in arr
, we are looking for n/2 = 2
pairs.
Following the solution steps:
-
Calculate the remainders of each element when divided by
k = 3
:2 % 3 = 2
4 % 3 = 1
1 % 3 = 1
5 % 3 = 2
The remainders are[2, 1, 1, 2]
.
-
Count the frequency of each remainder using the
Counter
:- Remainder
1
appears2
times. - Remainder
2
appears2
times.
- Remainder
-
Verify the first condition for elements with zero remainders:
- Our example does not have any element with a remainder of
0
, so we can skip this.
- Our example does not have any element with a remainder of
-
Verify the second condition for elements with non-zero remainders:
- Check each
i
from1
tok - 1
, which in this case is just1
and2
sincek = 3
. - For
i = 1
: Count is2
. - For
k - i = 3 - 1 = 2
: Count is2
. - Since the counts are equal for
i
andk - i
, the condition is met.
- Check each
Since the array only has non-zero remainders and each remainder i
has an equal count to k - i
, we have successfully verified that it is possible to partition the array into n/2
pairs where the sum of each pair is divisible by k
. Thus, the function would return true
.
The corresponding Python function would process the information as follows:
from collections import Counter
def canArrange(arr: List[int], k: int) -> bool:
cnt = Counter(x % k for x in arr)
# Since there is no remainder of 0, we skip checking cnt[0] % 2
# Validate the second condition using a list comprehension and all()
return all(cnt[i] == cnt[k - i] for i in range(1, k))
# Example array and k
arr = [2, 4, 1, 5]
k = 3
# Call the function with the example inputs
print(canArrange(arr, k)) # Output: True
By adhering to the solution steps, we are given a working example of the algorithm applied to this simple array, confirming the algorithm's correctness in this scenario.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def canArrange(self, arr: List[int], k: int) -> bool:
5 # Count the frequency of each remainder when each element in arr is divided by k
6 remainder_count = Counter(x % k for x in arr)
7
8 # Check if the number of elements that are divisible by k is even
9 if remainder_count[0] % 2 != 0:
10 return False
11
12 # Check if each non-zero remainder has a complementary count of elements
13 # Such that remainder + complementary = k
14 # The counts of remainder and its complementary need to be the same
15 for remainder in range(1, k):
16 if remainder_count[remainder] != remainder_count[k - remainder]:
17 return False
18
19 # All checks have passed, hence return True
20 return True
21
1class Solution {
2
3 public boolean canArrange(int[] arr, int k) {
4 // Create an array to store counts of modulo results
5 int[] count = new int[k];
6
7 // Loop through each number in the input array
8 for (int number : arr) {
9 // Increment the count at the index equal to the number's modulo k,
10 // taking into account negative numbers by adding k before modding
11 count[(number % k + k) % k]++;
12 }
13
14 // Check pairs for each possible modulo result except for 0
15 for (int i = 1; i < k; ++i) {
16 // For a valid pair, count of modulo i should be equal to count of modulo (k - i)
17 if (count[i] != count[k - i]) {
18 // If they are not equal, the condition is not met, so return false
19 return false;
20 }
21 }
22
23 // Check that count of numbers that are exactly divisible by k (modulo result is 0)
24 // is an even number since they need to be paired among themselves
25 return count[0] % 2 == 0;
26 }
27}
28
1class Solution {
2public:
3 // This function checks if it's possible to rearrange 'arr' such that the sum of every pair of elements is divisible by 'k'.
4 bool canArrange(vector<int>& arr, int k) {
5 // Create a count array to store frequencies of mod values
6 vector<int> count(k, 0);
7
8 // Increment the count for each element's mod value with 'k', properly handling negative numbers
9 for (int number : arr) {
10 int modValue = ((number % k) + k) % k;
11 ++count[modValue];
12 }
13
14 // Check pairs from 1 to k-1. For every 'i', there must be equal number of elements with 'k-i' as mod.
15 for (int i = 1; i < k; ++i) {
16 if (count[i] != count[k - i]) {
17 // If counts are not equal, pairs cannot be formed to satisfy the condition.
18 return false;
19 }
20 }
21
22 // The count of elements evenly divisible by 'k' must be even for them to be paired.
23 return count[0] % 2 == 0;
24 }
25};
26
1// Function checks if it's possible to rearrange 'arr' so that the sum of every pair of elements is divisible by 'k'.
2function canArrange(arr: number[], k: number): boolean {
3 // Create an array to store frequencies of mod values
4 let modCount: number[] = new Array(k).fill(0);
5
6 // Increment the count for each element's mod value with 'k',
7 // properly handling negative numbers
8 arr.forEach(number => {
9 let modValue: number = ((number % k) + k) % k;
10 modCount[modValue]++;
11 });
12
13 // Check pairs from 1 to k - 1. For every 'i', there must be an equal number of elements with 'k - i' as their mod value.
14 for (let i = 1; i < k; i++) {
15 if (modCount[i] !== modCount[k - i]) {
16 // If counts are not equal, pairs cannot be formed to satisfy the condition.
17 return false;
18 }
19 }
20
21 // The count of elements evenly divisible by 'k' must be even for them to be paired successfully.
22 return modCount[0] % 2 === 0;
23}
24
25// Example usage:
26// let result: boolean = canArrange([1, 2, 3, 4, 5, 10, -10], 5);
27// console.log(result); // This should output true or false based on the array and k value.
28
Time and Space Complexity
Time Complexity
The time complexity of the given code can be analyzed by looking at the operations performed:
- The list comprehension
x % k for x in arr
iterates over each element inarr
, resulting inO(n)
time complexity, wheren
is the length ofarr
. - The
Counter
from the standardcollections
module constructs the frequency dictionary in once againO(n)
time complexity. - The
return
statement consists of two parts:- Checking if
cnt[0] % 2 == 0
is a constant timeO(1)
operation because we access a dictionary key and then check for evenness. - The list comprehension
all(cnt[i] == cnt[k - i] for i in range(1, k))
could iterate up tok
times. In the worst case, this isO(k)
. However, since there are only 'n' unique modulo results possible (all elementsx
inarr
are used to computex % k
), we are effectively iterating up tomin(n, k)
, henceO(min(n, k))
.
- Checking if
Based on these observations, the total time complexity is O(n) + O(1) + O(min(n, k))
which simplifies to O(n + min(n, k))
. Since n
and k
are independent variables, we cannot simplify this further without knowing the relationship between n
and k
.
Space Complexity
The space complexity is determined by the auxiliary space used by the program. In this case:
- The frequency dictionary
cnt
may contain up tomin(n, k)
different keys (since these are the unique modulo results) and therefore has a space complexity ofO(min(n, k))
. - The space complexity for the list comprehension is
O(1)
since it's not stored but used directly in theall
function.
Consequently, the space complexity of the whole code is dominated by the space requirement of the frequency dictionary, which is O(min(n, k))
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used in a depth first search?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!