Count Array Pairs Divisible by K

Count Array Pairs Divisible by K

What is this problem about?

The Count Array Pairs Divisible by K coding problem asks you to find the number of pairs of indices (i, j) such that i < j and the product nums[i] * nums[j] is divisible by k. Given that the array can be very large, a simple O(N^2) check of all pairs is too slow.

Why is this asked in interviews?

Qualcomm and PayPal use the Count Array Pairs Divisible by K interview question to test your knowledge of Number Theory, specifically Greatest Common Divisor (GCD). It evaluates your ability to optimize a product-based divisibility condition using frequency maps of GCD values. It’s a "Hard" problem because it requires a deep mathematical insight to reach the optimal O(N * sqrt(K)) solution.

Algorithmic pattern used

The problem uses GCD and Frequency Maps.

1. For each number x in the array, its contribution to the product being divisible by k is captured by gcd(x, k).
2. Store the frequencies of these GCD values in a map.
3. Two numbers a and b form a valid pair if (gcd(a, k) * gcd(b, k)) % k == 0.
4. Iterate through the pairs of GCDs in the map and count the valid combinations.

Example explanation

nums = [1, 2, 3, 4, 5], k = 2

1. Calculate gcd(x, 2) for each x:
   • gcd(1, 2) = 1
   • gcd(2, 2) = 2
   • gcd(3, 2) = 1
   • gcd(4, 2) = 2
   • gcd(5, 2) = 1
2. GCD Map: {1: 3, 2: 2}.
3. Pairs from map:
   • (1, 2): 1 * 2 = 2 (Divisible by 2). Pairs = 3 * 2 = 6.
   • (2, 2): 2 * 2 = 4 (Divisible by 2). Pairs = 2 * (2-1) / 2 = 1. Total = 7.

Common mistakes candidates make

• Brute Force: Trying to check all pairs O(N^2), which will time out for N=10^5.
• Modulo Logic: Not realizing that (a * b) % k == 0 is equivalent to checking if the product of their GCDs with k is divisible by k.
• Duplicate Pairs: Counting the same pair twice or not handling the i < j constraint correctly when using the map.

Interview preparation tip

Whenever a problem involves products and divisibility, always think about Greatest Common Divisor. It’s the most powerful tool for reducing large numbers into their "useful" factors relative to a target k.