Count Equal and Divisible Pairs in an Array

Easy
504.

Count Equal and Divisible Pairs in an Array

Count Equal and Divisible Pairs in an Array is an easy coding problem on arrays, asked in Amazon and Wipro interviews.

Given a 0-indexed integer array nums and an integer k, return the number of index pairs (i, j) with i < j such that nums[i] == nums[j] and i * j is divisible by k.

Example 1

Input
nums = [3,1,2,2,2,1,3], k = 2
Output
4
Explanation
The qualifying pairs are (0,6), (2,3), (2,4) and (3,4).

Example 2

Input
nums = [1,2,3,4], k = 1
Output
0
Explanation
All values are distinct.

Example 3

Input
nums = [5,5,5], k = 2
Output
3
Explanation
(0,1) and (0,2) have product 0, and (1,2) has product 2 — all divisible by 2.

Constraints

  • 1 <= nums.length <= 100
  • 1 <= nums[i], k <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var countPairs = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Equal and Divisible Pairs in an Array — Solution

Count Equal and Divisible Pairs in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Count Equal and Divisible Pairs in an Array is an easy coding problem on arrays, asked in Amazon and Wipro interviews.

  • Difficulty: Easy
  • Topics: Arrays
  • Asked at: Amazon, Wipro
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given a 0-indexed integer array nums and an integer k, return the number of index pairs (i, j) with i < j such that nums[i] == nums[j] and i * j is divisible by k.

Example 1

Input: nums = [3,1,2,2,2,1,3], k = 2
Output: 4
Explanation: The qualifying pairs are (0,6), (2,3), (2,4) and (3,4).

Example 2

Input: nums = [1,2,3,4], k = 1
Output: 0
Explanation: All values are distinct.

Example 3

Input: nums = [5,5,5], k = 2
Output: 3
Explanation: (0,1) and (0,2) have product 0, and (1,2) has product 2 — all divisible by 2.

Constraints

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

Hints for Count Equal and Divisible Pairs in an Array

  1. Hint 1

    The array is short, so checking every pair is well within budget.

  2. Hint 2

    Both conditions must hold — equal values and i * j % k == 0.

  3. Hint 3

    Only pairs with i < j count, so the inner loop should start at i + 1.

How to solve Count Equal and Divisible Pairs in an Array

With n <= 100 the total pair count is at most 4950, so the direct double loop is the right tool — no cleverness required.

Approach

  1. Loop i over all indices and j over indices after i.
  2. Count the pair when nums[i] == nums[j] and (i * j) % k == 0.
  3. Return the count.

Why it works

The double loop enumerates each unordered index pair exactly once, and both conditions are checked directly, so the count is exact by construction.

Complexity

  • Time — O(n²)
  • Space — O(1)

Pitfalls

  • Starting the inner loop at 0 counts each pair twice and admits i == j.
  • i * j uses indices, not values — a common misreading.
  • Index 0 pairs with everything as far as divisibility goes, since 0 * j == 0 is divisible by any k.

Reference solution

Python

from typing import List

def countPairs(nums: List[int], k: int) -> int:
    count = 0
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] == nums[j] and (i * j) % k == 0:
                count += 1
    return count

Java

public static int countPairs(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] && (i * j) % k == 0) count++;
        }
    }
    return count;
}

C++

int countPairs(vector<int>& nums, int k) {
    int count = 0;
    int n = (int) nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] == nums[j] && (i * j) % k == 0) count++;
        }
    }
    return count;
}

JavaScript

var countPairs = function(nums, k) {
    let count = 0;
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] === nums[j] && (i * j) % k === 0) count++;
        }
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays