Leetcode 1497: Check If Array Pairs Are Divisible by k
You are given an array of integers arr of even length n and an integer k. The task is to check if you can divide the array into exactly n / 2 pairs such that the sum of each pair is divisible by k. Return true if it’s possible to divide the array into valid pairs, otherwise return false.
Problem
Approach
Steps
Complexity
Input: The input consists of an array arr of even length n and an integer k.
Example: arr = [3, 1, 2, 6, 4, 10], k = 5
Constraints:
• 1 <= n <= 10^5
• n is even.
• -10^9 <= arr[i] <= 10^9
• 1 <= k <= 10^5
Output: Return true if it is possible to divide the array into valid pairs such that the sum of each pair is divisible by k. Otherwise, return false.
Example: Output: true
Constraints:
• The length of the array is even.
Goal: The goal is to check whether each element of the array can be paired with another element such that their sum is divisible by k.
Steps:
• Initialize an array to count the frequency of the remainders when dividing each element by k.
• For each element, compute its remainder when divided by k, and store this in the frequency array.
• Check if the frequency of elements with remainder 0 is even.
• For each non-zero remainder, check if the frequency of elements with remainder r is equal to the frequency of elements with remainder k-r.
Goal: The array has even length n, and k is a positive integer.
Steps:
• 1 <= n <= 10^5
• n is even.
• -10^9 <= arr[i] <= 10^9
• 1 <= k <= 10^5
Assumptions:
• The input array always has an even number of elements.
• Input: arr = [3, 1, 2, 6, 4, 10], k = 5
• Explanation: The valid pairs are (3, 7), (1, 9), (2, 8), and (4, 10), all of which sum to multiples of 5.
• Input: arr = [1, 2, 3, 4, 5, 6], k = 10
• Explanation: There are no valid pairs whose sum is divisible by 10.
Approach: To solve this problem, we can use a frequency map to track the remainders of the array elements when divided by k. By checking the frequencies of complementary remainders, we can determine if it's possible to form the required pairs.
Observations:
• The problem boils down to checking remainders when dividing elements by k.
• If the frequency of remainders can be paired correctly, then the array can be divided as required.
Steps:
• Create a frequency map to store the count of each remainder modulo k.
• For each element in the array, calculate the remainder when divided by k and update the frequency map.
• Ensure that for every remainder r, there are an equal number of elements with remainder k - r, except for remainder 0, which must occur an even number of times.
Empty Inputs:
• The array cannot be empty as its length is guaranteed to be even.
Large Inputs:
• The solution must handle arrays with sizes up to 10^5.
Special Values:
• If k is 1, any pair of numbers will satisfy the condition since any sum is divisible by 1.
Constraints:
• The array must always have an even number of elements.
bool canArrange(vector<int>& arr, int k) {
vector<int> frq(k, 0);
for(int num : arr) {
num %= k;
if (num < 0) num += k;
frq[num]++;
}
if(frq[0]%2 != 0) return false;
for(int i = 1; i <= k/2; i++)
if(frq[i] != frq[k - i]) return false;
return true;
}
1 : Function Declaration
bool canArrange(vector<int>& arr, int k) {
The function `canArrange` takes an array `arr` and an integer `k` as input, and returns a boolean indicating whether the array can be rearranged such that the sum of any two elements is divisible by `k`.
2 : Vector Initialization
vector<int> frq(k, 0);
Initialize a vector `frq` of size `k` to store the frequency of remainders when elements of the array are divided by `k`. Each element in `frq` is initially set to 0.
3 : Loop
for(int num : arr) {
Loop through each element `num` in the array `arr`.
4 : Modulo Operation
num %= k;
Take the remainder when `num` is divided by `k` and update `num` to this value.
5 : Negative Adjustment
if (num < 0) num += k;
If `num` is negative after the modulo operation, adjust it by adding `k` to ensure the remainder is non-negative.
6 : Frequency Update
frq[num]++;
Increment the frequency of the remainder `num` in the vector `frq`.
7 : Check Zero Frequency
if(frq[0] % 2 != 0) return false;
Check if the frequency of elements that give a remainder of 0 when divided by `k` is even. If it's odd, return `false` because pairs can't be formed.
8 : Pairing Check
for(int i = 1; i <= k / 2; i++)
Loop through each possible remainder from 1 to `k/2` to check if the frequency of elements with remainder `i` matches the frequency of elements with remainder `k - i`.
9 : Pair Frequency Check
if(frq[i] != frq[k - i]) return false;
If the frequency of elements with remainder `i` does not match the frequency of elements with remainder `k - i`, return `false` because they can't be paired.
10 : Return True
return true;
If all checks pass, return `true` indicating that the array can be rearranged to satisfy the pairing condition.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) as we only iterate through the array once and perform constant time operations for each element.
Best Case: O(k)
Worst Case: O(k)
Description: The space complexity is O(k) to store the frequency map of remainders modulo k.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus