Count Array Pairs Divisible By K - Leetcode Solution

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:

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

5. 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).

1