Count Array Pairs Divisible by K solution and explanation
9 more videos on this problem
Hard Coding Test Problem | Leetcode Weekly Episode 5 | Leetcode 2183 | Number TheoryVivek Gupta · 10:26 · 6K views
2183. Count Array Pairs Divisible by K || LeetCode 2183 || LeetCode Weekly Contest 281Bro Coders · 19:19 · 6K views
2183. Count Array Pairs Divisible by K | Leetcode 2183 | Contest 281 | Maps Math🔥🔥Coding Decoded · 8:29 · 5K views
2183. Count Array Pairs Divisible by K | Leetcode Weekly Contest 281 | Hitesh TripathiCode Era · 15:23 · 2K views
Count Array Pairs Divisible by K | LeetCode 2183 | Hard ProblemCodeYotta · 11:43 · 699 views
2183. Count Array Pairs Divisible by K (Leetcode Hard)Programming Live with Larry · 54:53 · 605 views
L9. Count Array Pairs Divisible by K || Leetcode | HashMap | C++ | Java | #90dayschallenge | #day9Jasmeen Kaur · 23:26 · 308 views
Leetcode 2183 Count Array Pairs Divisible by KMath Geeks · 3:07 · 175 views
Count Array Pairs Divisible by K - LeetCode 2183 | Best Intuition + Easy Approach #coding #leetcodeCodehurdle · 24:30 · 79 views
Leetcode 2183. Count Array Pairs Divisible by K (math divisors)LetsCode · 14:05 · 36 views
The problem
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 - 1andnums[i] * nums[j]is divisible byk.
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 <= 1051 <= 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.
def count_pairs_divisible_by_k(nums, k):
count = 0
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if (nums[i] * nums[j]) % k == 0:
count += 1
return count
# Example usage
nums = [1, 2, 3, 4, 5]
k = 2
print(count_pairs_divisible_by_k(nums, k))public class Solution {
public int countPairsDivisibleByK(int[] nums, int k) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if ((nums[i] * nums[j]) % k == 0) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 3, 4, 5};
int k = 2;
System.out.println(sol.countPairsDivisibleByK(nums, k));
}
}#include <iostream>
#include <vector>
int countPairsDivisibleByK(const std::vector<int>& nums, int k) {
int n = nums.size();
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if ((nums[i] * nums[j]) % k == 0) {
count++;
}
}
}
return count;
}
int main() {
std::vector<int> nums = {1, 2, 3, 4, 5};
int k = 2;
std::cout << countPairsDivisibleByK(nums, k) << std::endl;
return 0;
}function countPairsDivisibleByK(nums, k) {
let count = 0;
let n = nums.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if ((nums[i] * nums[j]) % k === 0) {
count++;
}
}
}
return count;
}
const nums = [1, 2, 3, 4, 5];
const k = 2;
console.log(countPairsDivisibleByK(nums, k));#include <stdio.h>
int countPairsDivisibleByK(int* nums, int n, int k) {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if ((nums[i] * nums[j]) % k == 0) {
count++;
}
}
}
return count;
}
int main() {
int nums[] = {1, 2, 3, 4, 5};
int k = 2;
int n = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", countPairsDivisibleByK(nums, n, k));
return 0;
}using System;
public class Solution {
public int CountPairsDivisibleByK(int[] nums, int k) {
int count = 0;
for (int i = 0; i < nums.Length; i++) {
for (int j = i + 1; j < nums.Length; j++) {
if ((nums[i] * nums[j]) % k == 0) {
count++;
}
}
}
return count;
}
public static void Main() {
int[] nums = { 1, 2, 3, 4, 5 };
int k = 2;
Solution sol = new Solution();
Console.WriteLine(sol.CountPairsDivisibleByK(nums, k));
}
}In Python, the program uses nested loops to find pairs where the product is divisible by k, then increments the count.
Time Complexity: O(n^2) - due to nested loops for all pairs.
Space Complexity: O(1) - minimal additional space is used.
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.
from collections import defaultdict
def count_pairs_divisible_by_k(nums, k):
freq = defaultdict(int)
count = 0
for num in nums:
rem = num % k
complement = (k - rem) % k
count += freq[complement]
freq[rem] += 1
return count
# Example usage
nums = [1, 2, 3, 4, 5]
k = 2
print(count_pairs_divisible_by_k(nums, k))import java.util.HashMap;
import java.util.Map;
public class Solution {
public int countPairsDivisibleByK(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
int count = 0;
for (int num : nums) {
int rem = num % k;
int complement = (k - rem) % k;
count += freq.getOrDefault(complement, 0);
freq.put(rem, freq.getOrDefault(rem, 0) + 1);
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 3, 4, 5};
int k = 2;
System.out.println(sol.countPairsDivisibleByK(nums, k));
}
}#include <iostream>
#include <vector>
#include <unordered_map>
int countPairsDivisibleByK(const std::vector<int>& nums, int k) {
std::unordered_map<int, int> freq;
int count = 0;
for (int num : nums) {
int rem = num % k;
int complement = (k - rem) % k;
count += freq[complement];
freq[rem]++;
}
return count;
}
int main() {
std::vector<int> nums = {1, 2, 3, 4, 5};
int k = 2;
std::cout << countPairsDivisibleByK(nums, k) << std::endl;
return 0;
}function countPairsDivisibleByK(nums, k) {
const freq = new Map();
let count = 0;
for (const num of nums) {
const rem = num % k;
const complement = (k - rem) % k;
if (freq.has(complement)) {
count += freq.get(complement);
}
freq.set(rem, (freq.get(rem) || 0) + 1);
}
return count;
}
const nums = [1, 2, 3, 4, 5];
const k = 2;
console.log(countPairsDivisibleByK(nums, k));#include <stdio.h>
#include <string.h>
int gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
int countPairsDivisibleByK(int* nums, int n, int k) {
int freq[k];
memset(freq, 0, sizeof(freq));
int count = 0;
for (int i = 0; i < n; i++) {
int rem = nums[i] % k;
int complement = (k - rem) % k;
count += freq[complement];
freq[rem]++;
}
return count;
}
int main() {
int nums[] = {1, 2, 3, 4, 5};
int k = 2;
int n = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", countPairsDivisibleByK(nums, n, k));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int CountPairsDivisibleByK(int[] nums, int k) {
Dictionary<int, int> freq = new Dictionary<int, int>();
int count = 0;
foreach (int num in nums) {
int rem = num % k;
int complement = (k - rem) % k;
if (freq.ContainsKey(complement)) {
count += freq[complement];
}
if (freq.ContainsKey(rem)) {
freq[rem]++;
} else {
freq[rem] = 1;
}
}
return count;
}
public static void Main() {
int[] nums = { 1, 2, 3, 4, 5 };
int k = 2;
Solution sol = new Solution();
Console.WriteLine(sol.CountPairsDivisibleByK(nums, k));
}
}The Python approach uses a defaultdict to manage frequencies of remainders. As we process each element, we update counts based on remainder complement needed to reach divisibility.
Time Complexity: O(n) - iterates over list once.
Space Complexity: O(k) - requires storage for frequencies.
Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2) - due to nested loops for all pairs. |
| Optimized Approach Using Remainders | Time Complexity: O(n) - iterates over list once. |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Check | O(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 k | General case and interview settings with large n |
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.