Solution Explanation for Count Array Pairs Divisible by K

This problem asks us to find the number of pairs (i, j) in an array nums such that 0 <= i < j <= n-1 and nums[i] * nums[j] is divisible by k. A brute-force approach would have O(n²) time complexity, which is inefficient for large arrays. We can optimize this using a more efficient approach.

Optimized Approach:

The key observation is that nums[i] * nums[j] is divisible by k if and only if (nums[i] * nums[j]) mod k == 0. We can leverage this property to avoid unnecessary multiplications. Instead of directly checking the divisibility of the product, we can analyze the divisibility of individual numbers.

We use a frequency array freq to store the frequency of each remainder when nums[i] is divided by k. Then, we iterate through all possible pairs of remainders (r1, r2). If the product of the remainders (r1 * r2) mod k is 0, then we count the pairs that would produce such remainders.

Algorithm:

1. Frequency Counting: Create a frequency array freq of size k to store the count of each remainder when numbers in nums are divided by k.

2. Pair Counting: Iterate through all pairs of remainders (r1, r2) from 0 to k-1.

3. Divisibility Check: If (r1 * r2) % k == 0, we need to count the number of pairs with remainders r1 and r2. This is given by freq[r1] * freq[r2] if r1 != r2 (avoid double counting) and freq[r1] * (freq[r1] -1) / 2 if r1 == r2 (combinations within the same remainder).

4. Summation: Accumulate the counts from step 3 to get the total number of pairs.

Time Complexity: O(n + k²), where n is the length of nums and k is the given integer. The frequency counting is O(n), and the pair iteration is O(k²). In most cases, k is significantly smaller than n, making this approach much faster than the brute force O(n²) solution.

Space Complexity: O(k), the space used by the frequency array.

Code Implementation (Python):

def countPairs(nums, k):
    n = len(nums)
    freq = [0] * k
    for num in nums:
        freq[num % k] += 1
 
    count = 0
    for r1 in range(k):
        for r2 in range(k):
            if (r1 * r2) % k == 0:
                if r1 != r2:
                    count += freq[r1] * freq[r2]
                else:
                    count += freq[r1] * (freq[r1] - 1) // 2
    return count // 2
 

Code Implementation (Java):

class Solution {
    public long countPairs(int[] nums, int k) {
        int n = nums.length;
        int[] freq = new int[k];
        for (int num : nums) {
            freq[num % k]++;
        }
 
        long count = 0;
        for (int r1 = 0; r1 < k; r1++) {
            for (int r2 = 0; r2 < k; r2++) {
                if ((r1 * r2) % k == 0) {
                    if (r1 != r2) {
                        count += (long) freq[r1] * freq[r2];
                    } else {
                        count += (long) freq[r1] * (freq[r1] - 1) / 2;
                    }
                }
            }
        }
        return count / 2;
    }
}

Code Implementation (C++):

class Solution {
public:
    long long countPairs(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long> freq(k, 0);
        for (int num : nums) {
            freq[num % k]++;
        }
 
        long long count = 0;
        for (int r1 = 0; r1 < k; r1++) {
            for (int r2 = 0; r2 < k; r2++) {
                if ((r1 * r2) % k == 0) {
                    if (r1 != r2) {
                        count += freq[r1] * freq[r2];
                    } else {
                        count += freq[r1] * (freq[r1] - 1) / 2;
                    }
                }
            }
        }
        return count / 2;
    }
};

Code Implementation (Go):

func countPairs(nums []int, k int) int64 {
	n := len(nums)
	freq := make([]int, k)
	for _, num := range nums {
		freq[num%k]++
	}
 
	count := int64(0)
	for r1 := 0; r1 < k; r1++ {
		for r2 := 0; r2 < k; r2++ {
			if (r1*r2)%k == 0 {
				if r1 != r2 {
					count += int64(freq[r1]) * int64(freq[r2])
				} else {
					count += int64(freq[r1]) * int64(freq[r1]-1) / 2
				}
			}
		}
	}
	return count / 2
}

These codes implement the optimized algorithm described above. Remember that the //2 at the end is because we are counting ordered pairs (i,j) where i<j, and we initially counted all pairs without considering the order.