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 total count of pairs 
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; 
}