Count Equal and Divisible Pairs in an Array

Count Equal and Divisible Pairs in an Array

What is this problem about?

The Count Equal and Divisible Pairs in an Array interview question asks you to find the number of pairs of indices (i, j) such that 0 <= i < j < n and two conditions are met:

1. nums[i] == nums[j]
2. (i * j) is divisible by a given integer k.

Why is this asked in interviews?

Microsoft and Meta use the Array interview pattern for this problem to test your ability to handle multi-condition checks on arrays. It’s an "Easy" difficulty problem where a simple brute-force approach is usually acceptable given the constraints. It evaluates your basic loop construction and modulo arithmetic skills.

Algorithmic pattern used

The problem uses a Brute Force / Enumeration pattern.

1. Iterate through all pairs (i, j) using two nested loops where the inner loop starts from i + 1.
2. For each pair, check if nums[i] == nums[j].
3. If they are equal, check if (i * j) % k == 0.
4. Increment a counter if both conditions are true.

Example explanation

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

1. Pair (0, 6): nums[0]=3, nums[6]=3. 0 * 6 = 0. 0 % 2 == 0. (Match!)
2. Pair (2, 3): nums[2]=2, nums[3]=2. 2 * 3 = 6. 6 % 2 == 0. (Match!)
3. Pair (2, 4): nums[2]=2, nums[4]=2. 2 * 4 = 8. 8 % 2 == 0. (Match!)
4. Pair (3, 4): nums[3]=2, nums[4]=2. 3 * 4 = 12. 12 % 2 == 0. (Match!) Result: 4.

Common mistakes candidates make

• i < j constraint: Not starting the inner loop at i + 1, which leads to double-counting pairs.
• Divisibility of 0: Forgetting that 0 % k is always 0. Since indices are 0-based, the first index 0 will always satisfy the product condition.
• Complexity: Over-engineering the solution with a Hash Map when O(N^2) is perfectly fine for the given constraints (e.g., N=100).

Interview preparation tip

Always check the constraints. If N is small (like 100), O(N^2) is the expected solution. Don't waste time on complex optimizations unless the constraints are much larger (e.g., 10^5).