Scale Engineer

Count Array Pairs Divisible by K

Hard
#1988Time: O(N<sup>2</sup>) - Where N is the number of elements in `nums`. The nested loops result in a quadratic number of operations, as we check every possible pair.Space: O(1) - We only use a constant amount of extra space for the counter and loop variables.1 company
Patterns
MathNumber Theory
Data structures
Array
Companies
PayPal

Prompt

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 and
  • nums[i] * nums[j] is divisible by k.

 

Example 1:

Input: nums = [1,2,3,4,5], k = 2
Output: 7
Explanation: 
The 7 pairs of indices whose corresponding products are divisible by 2 are
(0, 1), (0, 3), (1, 2), (1, 3), (1, 4), (2, 3), and (3, 4).
Their products are 2, 4, 6, 8, 10, 12, and 20 respectively.
Other pairs such as (0, 2) and (2, 4) have products 3 and 15 respectively, which are not divisible by 2.

Example 2:

Input: nums = [1,2,3,4], k = 5
Output: 0
Explanation: There does not exist any pair of indices whose corresponding product is divisible by 5.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i], k <= 105

Approaches

3 approaches with complexity analysis and trade-offs.

The most straightforward way to solve this problem is to check every possible pair of elements in the array. This approach uses two nested loops to generate all pairs (i, j) such that 0 <= i < j < n. For each pair, it computes their product and checks if it's divisible by k.

Algorithm

  • Initialize a counter count to 0.
  • Use a nested loop to iterate through all unique pairs of indices (i, j) where i < j.
  • For each pair, calculate the product p = (long)nums[i] * nums[j]. It's important to cast to long to prevent potential integer overflow since nums[i] and nums[j] can be up to 10<sup>5</sup>.
  • Check if the product p is divisible by k using the modulo operator: p % k == 0.
  • If the product is divisible by k, increment the count.
  • After checking all pairs, return the final count.

Walkthrough

This method involves a brute-force check of all possible pairs. The outer loop runs from the first element to the second-to-last element, and the inner loop runs from the element after the outer loop's current element to the last one. This ensures that every pair (i, j) with i < j is considered exactly once. Inside the inner loop, we perform the multiplication and the divisibility check. A counter is maintained to keep track of the number of valid pairs found.

class Solution {    public long countPairs(int[] nums, int k) {        long count = 0;        int n = nums.length;        for (int i = 0; i < n; i++) {            for (int j = i + 1; j < n; j++) {                if (((long) nums[i] * nums[j]) % k == 0) {                    count++;                }            }        }        return count;    }}

Complexity

Time

O(N<sup>2</sup>) - Where N is the number of elements in `nums`. The nested loops result in a quadratic number of operations, as we check every possible pair.

Space

O(1) - We only use a constant amount of extra space for the counter and loop variables.

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires no extra space besides a few variables.

Cons

  • This approach is very slow and will result in a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints (N up to 10<sup>5</sup>).

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem