# Solution For Count Array Pairs Divisible By K

Problem Statement:

Given an integer array nums and an integer k, return the number of pairs (i, j) where i < j such that abs(nums[i] – nums[j]) is divisible by k.

Example:

Input: nums = [1,2,3,4,5], k = 2
Output: 4
Explanation: There are four pairs (i, j) with i < j and abs(nums[i] – nums[j]) is divisible by k:
– (1, 3): abs(1 – 4) = 3, which is divisible by 2.
– (1, 5): abs(1 – 5) = 4, which is divisible by 2.
– (2, 4): abs(2 – 4) = 2, which is divisible by 2.
– (3, 5): abs(3 – 5) = 2, which is divisible by 2.

Solution:

We can solve this problem in O(N) time and O(K) space complexity using the following algorithm:

1. Create an array of size K and initialize all its elements to 0.

2. Traverse through the given array nums and for each element num in the array, increment the count of num % K in the array created in step 1.

3. Initialize the result variable to 0.

4. Traverse through the given array nums and for each element num in the array, do the following:

5. Calculate the remainder of num divided by K.
6. If remainder is 0, then increment the result variable by the count of 0s in the array created in step 1.
7. Otherwise, increment the result variable by the count of (K – remainder) in the array created in step 1.

8. Return the result variable as the final answer.

Let’s implement the above algorithm in Python:

def countPairs(nums, k):
# Step 1
counts = [0] * k
for num in nums:
counts[num % k] += 1

``````# Step 2
res = 0
for num in nums:
rem = num % k
if rem == 0:
res += counts[0]
else:
res += counts[k - rem]

# Step 3
return res // 2
``````

In this solution, we are traversing the nums array twice, which makes it O(N) time complexity. We also have a counts array of size K, which makes the space complexity O(K). Here, we are returning res // 2 because we are counting each pair twice (once for i, j and then again for j, i).

## Step by Step Implementation For Count Array Pairs Divisible By K

```class Solution {
public int countPairs(int[] arr, int k) {
int count = 0;
HashMap map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
if (!map.containsKey(arr[i])) {
map.put(arr[i], 1);
} else {
map.put(arr[i], map.get(arr[i]) + 1);
}
}
for (int i = 0; i < arr.length; i++) {
if (map.containsKey(arr[i] + k)) {
count += map.get(arr[i] + k);
}
}
return count;
}
}```
```def count_array_pairs_divisible_by_k(arr, k):

# Initialize result
count = 0

# Consider all possible pairs
for i in range(0, len(arr)):
for j in range(i + 1, len(arr)):

# If i & j are divisible by k,
# then increment count
if ((arr[i] + arr[j]) % k == 0):
count += 1

return count```
```/**
* @param {number} k
* @param {number[]} nums
* @return {number}
*/
var countPairs = function(k, nums) {
// create a hashmap to store the remainder of each number when divided by k
let map = {};

// go through each number in the array
for (let i = 0; i < nums.length; i++) {
// get the remainder of the current number when divided by k
let remainder = nums[i] % k;

// if the remainder is not in the hashmap, add it
if (!(remainder in map)) {
map[remainder] = 1;
}
// if the remainder is in the hashmap, increment the count
else {
map[remainder]++;
}
}

// initialize count to 0
let count = 0;

// go through each key in the hashmap
for (let key in map) {
// if the key is 0 or k/2 and the value is greater than 1, we need to divide the value choose 2 because we only want to count unique pairs
if ((key == 0 || key == k/2) && map[key] > 1) {
count += map[key] * (map[key] - 1) / 2;
}
// if the key is not 0 or k/2 and the value is greater than 0, we need to find the complement key and add the two values
else if (map[key] > 0) {
let complement = (k - key) % k;
count += map[key] * map[complement];
}
}

return count;
};```
```int countPairsDivisibleByK(int arr[], int n, int k)
{
// Create an empty map
map mp;

// Count occurrences of all remainders
for (int i = 0; i < n; i++)
mp[arr[i] % k]++;

// Initialize result
int result = 0;

// Traverse the map by only iterating
// till half as we are interested in
// symmetric pairs only
for (auto it = mp.begin(); it != mp.end(); it++)
{
// If there are more than one
// occurrences of remainder
if (it->second > 1)
result += (it->second * (it->second - 1)) / 2;

// If remainder is 0, update
// result directly
else if (it->first == 0)
result += it->second;

// Else find the symmetric
// remainder of current
// remainder and update the
// result if found
else
result += (it->second * mp[k - it->first]) ;
}

return result;
}```
```int countPairs(int[] arr, int k)
{
// Initialize result
int result = 0;

// Consider all possible pairs
// and check if it satisfies
// the condition or not
for (int i = 0; i < arr.length; i++)
for (int j = i + 1; j < arr.length; j++)
if ((arr[i] + arr[j]) % k == 0)
result++;

return result;
}```

Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]