Skip to main content
Talentd

Count Array Pairs Divisible by K - Solution & Explanation

HardArrayMathNumber Theory12 min readAsked at: Qualcomm, PayPal
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: Given an integer array nums and an integer k, count pairs (i, j) with i < j such that nums[i] * nums[j] is divisible by k. The challenge is avoiding the obvious quadratic pair check while still verifying the divisibility condition efficiently.

Approach 1: Brute Force Pair Check (O(n²) time, O(1) space)

The direct solution checks every pair in the array. Use two nested loops and compute (nums[i] * nums[j]) % k for each pair. If the remainder is zero, increment the count. This approach uses only constant extra memory and is easy to implement. However, it performs n(n-1)/2 multiplications and modulus operations, which becomes too slow when n grows large. Still useful as a baseline implementation and for verifying correctness during testing.

Approach 2: GCD Hashing with Number Theory (O(n log k) time, O(d) space)

The key observation: instead of checking the product directly, track how much each number contributes toward making a multiple of k. For each value x, compute g = gcd(x, k). This tells you the largest factor of k that x already covers. Two numbers form a valid pair when (g1 * g2) % k == 0. Maintain a hash map counting previously seen gcd values. For the current element, iterate over stored gcd values and add their frequencies when the product condition satisfies divisibility by k. After processing, store the current gcd in the map.

This transformation dramatically reduces the search space. Instead of comparing every pair of indices, you compare factor contributions relative to k. The number of distinct gcd values is bounded by the number of divisors of k, typically small. Each iteration performs a few gcd computations and hash lookups, making the solution scalable even for large arrays.

The optimized approach relies heavily on concepts from math and number theory, while the input itself is handled as a simple array. Understanding how gcd interacts with divisibility is the core trick that converts a quadratic search into a near‑linear solution.

Recommended for interviews: Interviewers expect the GCD + hash map optimization. The brute force approach demonstrates understanding of the requirement, but the optimized method shows you can apply number theory insights to reduce pair comparisons and achieve near-linear complexity.

Approach 1: Brute Force Approach

This approach involves checking every possible pair (i, j) to see if the product of the elements at these indices is divisible by k. It iterates over each pair and uses the modulus operator for the divisibility check.

The function iterates through each possible pair in the array. For each pair, it checks if the product of the numbers at these indices is divisible by k. If so, it increments the count.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) - due to the nested loops checking each pair.
Space Complexity: O(1) - only uses a constant amount of extra space.

Try this approach in the editor →

Approach 2: Optimized Approach Using Remainders

This approach reduces the number of checks needed by considering the divisibility of products using modular arithmetic. It involves counting occurrences of remainders of elements divided by factors of k. We precompute the frequency of these modules and use them to count divisible pairs effectively.

The C code uses an array to keep track of the frequency of each remainder when elements are divided by k. For each element, it calculates its remainder and looks for the complement remainder pair needed to form a product divisible by k.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) - each element is iterated once.
Space Complexity: O(k) - requires space for storing k frequencies.

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n^2) - due to the nested loops checking each pair.
Space Complexity: O(1) - only uses a constant amount of extra space.

Optimized Approach Using Remainders

Time Complexity: O(n) - each element is iterated once.
Space Complexity: O(k) - requires space for storing k frequencies.

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair CheckO(n²)O(1)Small arrays or quick correctness verification
GCD Hashing (Number Theory Optimization)O(n log k)O(d) where d is number of divisors of kGeneral case and interview settings with large n

Video Solution

Hard Coding Test Problem | Leetcode Weekly Episode 5 | Leetcode 2183 | Number Theory • Vivek Gupta • 6,151 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Count Array Pairs Divisible by K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check If Array Pairs Are Divisible by k

Next

Find the Number of Good Pairs I