Check If Array Pairs Are Divisible by k LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon PayPal Uber
QubleViews 3367

Problem Statement

Check If Array Pairs Are Divisible by k LeetCode Solution – Given an array of integers of even length n and an integer k.

We want to divide the array into exactly n/2 pairs such that the sum of each pair is divisible by k.

Return true  If you can find a way to do that or false otherwise.

Example for Check If Array Pairs Are Divisible by k LeetCode Solution:

Test Case 1:

Input:

inputArr = [1, 2, 3, 4, 5, 10, 6, 7, 8, 9],

k = 5

Output:

true

Test Case 2:

inputArr = [-1, 1, -2, 2, -3, 3, -4, 4]
k = 3

Output:

true

Test Case 3:

inputArr = [1, 2, 3, 4, 5, 6]
k = 10

Output:

false

Explanation for Check If Array Pairs Are Divisible by k LeetCode Solution:

i) For the first test case, we can divide them into pairs such as (1, 9), (2, 8), (3, 7), (4, 6), and (5, 10). The Sum of each of these pairs is divisible by 5. So the output is true.

ii) For the second test case, we can divide them into pairs such as (-1, 1), (-2, 2), (-3, 3), and (-4, 4). The Sum of each of these pairs is divisible by 3. So the output is true.

iii) For the third test case, there is no way we can divide the given array into pairs such as the sum of each pair is divisible by 10. So the output is false.

Approach

Idea:

Given 2 nums ‘a’ and ‘b’:
If a % k == x and b % k == k – x :
then (a + b) is divisible by k

1)  The basic idea is to keep the count of remainders of all elements of the given array.

2) Let’s say we stored the frequencies in the modFrequency array. the remainder 0 means the element is divisible by k. So modFrequency[0] keeps track of all the elements divisible by k. If one element is divisible by k, it can form pair with another element if and only if it is divisible by k otherwise the sum will not be divisible by k. So modFrequency[0] should be even.

3) For every element with remainder of i (i != 0) there should be a element with remainder k-i. Hence, modFrequency[i] should be equal to modFrequency[k-i] .

4) If any of the above conditions do not meet, we can return false, or else we will return true.

Code

Java Program for Check If Array Pairs Are Divisible by k

class Solution {
    public boolean canArrange(int[] arr, int k) {
        int[] modFrequency = new int[k];
        for(int num : arr){
            num %= k;
            if (num < 0) 
                num += k;
            modFrequency[num]++;
        }
        if(modFrequency[0] % 2 != 0) 
            return false;
        
        for(int i = 1; i <= k/2; i++)
            if(modFrequency[i] != modFrequency[k-i]) 
                 return false;
      
        return true;
    }
}

C++ Program for Check If Array Pairs Are Divisible by k

class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        map<int, int> modFrequency;
        for (int i = 0; i < arr.size(); ++i)
        {
            int num = arr[i] % k;
            if (num < 0)
                num += k;
            modFrequency[num]++;
        }
        if (modFrequency[0] % 2 != 0)
            return false;
        for (int i = 1; i <= k / 2; i++)
        {
            if (modFrequency[i] != modFrequency[k - i])
                return false;
        }
        return true;
    }
};

Complexity Analysis for Check If Array Pairs Are Divisible by k LeetCode Solution

Time Complexity

Here we are traversing the array once. If the size of the array is n, it will take O(n) time. We are using another loop for k/2 times. it will take O(k/2) or O(k) time. So the time complexity of the above code is basically Max(O(n), O(k)).

if n > k/2, Time complexity = O(n)

else Time complexity = O(k/2) ≡ O(k)

Space Complexity

The space complexity of the above code is O(k) because we are using a map or array to store the frequencies.

Reference: https://en.wikipedia.org/wiki/Remainder

Translate »