Check If Array Pairs Are Divisible By K - Leetcode Solution

The problem "Check If Array Pairs Are Divisible By K" on LeetCode asks us to check if there exists a pair of elements in the given array whose sum is divisible by the given integer k.

Approach:

To solve this problem, we can use the concept of remainder. We know that a number is divisible by k if its remainder when divided by k is 0. So, we can find the remainder of each element in the array when divided by k and store them in a frequency map.

After that, we can check for each pair of elements in the array whose sum is divisible by k. To find such pairs, we can take one element at a time, calculate its remainder when divided by k, and then look for another element whose remainder is such that its sum with the current remainder is divisible by k.

Algorithm:

1. Create an empty hash table/map.
2. Traverse the given array:
   • Calculate the remainder of each element when divided by k.
   • Increment the frequency of that remainder in the hash table.
3. Traverse the given array again:
   • Calculate the remainder of each element when divided by k.
   • Check if (k - remainder) is present in the hash table and its frequency is greater than 0.
     • If yes, return true as we have found the pair whose sum is divisible by k.
     • Else, decrement the frequency of the current remainder in the hash table.
4. If no such pair exists in the array, return false.

Pseudo-code:

function checkPairsDivisible(arr, k):
   frequencyMap = {}
   for i in range(len(arr)):
        remainder = arr[i] % k
        if remainder in frequencyMap:
            frequencyMap[remainder] += 1
        else:
            frequencyMap[remainder] = 1

   for i in range(len(arr)):
        remainder = arr[i] % k
        complement = (k - remainder) % k
        if complement in frequencyMap and frequencyMap[complement] > 0:
            return True
        else:
            frequencyMap[remainder] -= 1

   return False

Complexity Analysis:

• Time Complexity: O(n), where n is the size of the input array. We are traversing the array twice, and both the loops take O(n) time.
• Space Complexity: O(k), where k is the size of the frequency map. In the worst case, all the elements in the array are distinct, and hence, we will have k remainders in the frequency map.

1