Is Count Array Pairs Divisible by K easy or hard?

Count Array Pairs Divisible by K is classified as a Hard problem because the optimal solution requires recognizing a number theory pattern. Brute force is straightforward, but deriving the gcd-based optimization requires deeper understanding of divisibility properties.

Count Array Pairs Divisible by K Python/Java solution

Python and Java implementations typically compute gcd using built-in libraries (math.gcd in Python or Math.gcd equivalents). Each number's gcd with k is stored in a hash map, and compatible gcd values are checked to count valid pairs efficiently.

How to solve Count Array Pairs Divisible by K in O(n)?

A near-linear solution uses gcd(nums[i], k) to track the contribution of each element toward forming a multiple of k. Maintain a frequency map of gcd values seen so far. For each new element, combine it with compatible gcd entries whose product with the current gcd is divisible by k.

What is the best approach for Count Array Pairs Divisible by K?

The most efficient approach uses GCD hashing with number theory. For each number, compute gcd(nums[i], k) and store frequencies in a hash map. Two elements form a valid pair if the product of their gcd values is divisible by k. This reduces the complexity from O(n²) to about O(n log k).

Is Count Array Pairs Divisible by K asked at Google/Amazon/Meta?

Problems combining arrays with number theory and hash maps appear frequently in interviews at large companies such as Google, Amazon, and Meta. Variants involving gcd, divisibility, or pair counting are common in senior-level algorithm interviews.

What data structure is used in Count Array Pairs Divisible by K?

The optimized solution uses a hash map (dictionary) to store frequencies of gcd values relative to k. This allows constant-time updates and quick aggregation of valid pair counts during iteration.

What is the time complexity of Count Array Pairs Divisible by K?

The brute force solution runs in O(n²) time because it checks every pair of elements. The optimized solution using GCD and a hash map runs in roughly O(n log k), since each step computes gcd and checks a small set of stored divisor values.

Description Hints 2 Solution Video 10:26

2183. Count Array Pairs Divisible by K

Hard30.7% acceptance2 companies

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 <= 10⁵
1 <= nums[i], k <= 10⁵

Asked at 2 companies

PayPal Qualcomm

Topics

Hints open one at a time

Hint 1

For any element in the array, what is the smallest number it should be multiplied with such that the product is divisible by k?

Hint 2

The smallest number which should be multiplied with nums[i] so that the product is divisible by k is k / gcd(k, nums[i]). Now think about how you can store and update the count of such numbers present in the array efficiently.

10:26

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution