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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Array Pairs Divisible by K

Number: 2301

Difficulty: Hard

Paid? No

Companies: Amazon, PayPal

Problem Description

Given an integer array nums and an integer k, count the number of pairs (i, j) (with i < j) such that the product nums[i] * nums[j] is divisible by k.

Key Insights

  • Instead of checking every possible pair (which is O(n²)), transform each number by computing its greatest common divisor (gcd) with k.
  • For a number num, let g = gcd(num, k). Notice that g will always be a divisor of k.
  • The product nums[i] * nums[j] is divisible by k if and only if gcd(nums[i], k) * gcd(nums[j], k) is also divisible by k.
  • Use a frequency map to count occurrences of each gcd value.
  • Iterate over all pairs of these gcd values (taking care of duplicates) and count the valid pairs where the product of the two gcds is divisible by k.
  • Since the number of divisors of k is small, this results in a significantly reduced number of iterations.

Space and Time Complexity

Time Complexity: O(n + m²), where n is the length of nums and m is the number of divisors of k (m is small in practice). Space Complexity: O(m), for storing the counts of each divisor which divides k.

Solution

We start by iterating through the nums array and computing gcd(num, k) for each number. This value is used to categorize the numbers by their contribution towards divisibility by k. With these categories, we then iterate over every pair of categories. For a pair of divisors (g1, g2) to yield a product divisible by k, the product g1 * g2 should be divisible by k. We add to the answer either by pairing numbers within the same category or across different categories, taking care to avoid overcounting.

Code Solutions

import math
from collections import Counter

def countPairs(nums, k):
    # Dictionary to store frequency of each gcd computed from nums[i] and k
    gcd_count = Counter()
    
    # Calculate gcd for each num with k and update frequency map
    for num in nums:
        g = math.gcd(num, k)
        gcd_count[g] += 1

    # List out the unique gcd values
    divisors = list(gcd_count.keys())
    ans = 0

    # Check pairs of gcd values from the dictionary
    for i in range(len(divisors)):
        for j in range(i, len(divisors)):
            g1 = divisors[i]
            g2 = divisors[j]
            # If product of gcds is divisible by k, then all pairs of numbers
            # with these gcd values will yield a product divisible by k.
            if (g1 * g2) % k == 0:
                # If both numbers come from the same group, use combination formula
                if i == j:
                    ans += gcd_count[g1] * (gcd_count[g1] - 1) // 2
                else:
                    ans += gcd_count[g1] * gcd_count[g2]
    return ans

# Example usage:
print(countPairs([1,2,3,4,5], 2))  # Output: 7
← Back to All Questions