We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

Count Array Pairs Divisible by K

Difficulty: Hard

Problem Description

Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs (i, j) such that:

0 <= i < j <= n - 1
nums[i] * nums[j] is divisible by k.

Key Insights

A product is divisible by k if at least one of the numbers in the product has a factor that complements the other to make it divisible by k.
We can utilize the modulo operation to categorize numbers based on their remainders when divided by k.
For each number, we can determine how many numbers can pair with it to form a product that is divisible by k.

Space and Time Complexity

Time Complexity: O(n + k)
Space Complexity: O(k)

Solution

To solve this problem, we will follow these steps:

Create a frequency array to store the count of each remainder when the numbers in nums are divided by k.
Iterate through the nums array and for each number, calculate its remainder.
For each remainder, find the complement remainder that would make the product divisible by k.
Count valid pairs using the frequency array and ensure not to double count pairs.
Return the total count of valid pairs.

Code Solutions

def countPairs(nums, k):
    remainder_count = [0] * k
    count = 0

    # Count frequency of each remainder
    for num in nums:
        remainder = num % k
        remainder_count[remainder] += 1

    # Calculate valid pairs
    for i in range(k):
        if remainder_count[i] > 0:
            for j in range(i, k):
                if (i * j) % k == 0:
                    if i == j:
                        # Combination of pairs from same group
                        count += (remainder_count[i] * (remainder_count[i] - 1)) // 2
                    else:
                        count += remainder_count[i] * remainder_count[j]

    return count

← Back to All Questions