LeetCode Problem 2176

Difficulty: 🟢 Easy
Topics: Array

Solution

LeetCode 2176, Count Equal and Divisible Pairs in an Array

Problem Understanding

The problem gives us a 0-indexed integer array nums and an integer k. We need to count how many pairs of indices (i, j) satisfy all of the following conditions:

1. 0 <= i < j < n
2. nums[i] == nums[j]
3. (i * j) % k == 0

In other words, we are looking for pairs of positions in the array where the values are equal, and the product of the two indices is divisible by k.

The input array represents a sequence of integers. The output is a single integer representing the number of valid index pairs.

The constraints are small:

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

These limits tell us several important things. Since the array length is at most 100, even an O(n^2) solution is completely acceptable. A quadratic solution would perform at most about 10,000 pair checks, which is trivial for modern computers.

The problem also guarantees that all values are positive integers, so we do not need to worry about negative numbers or zero values in the array itself. However, indices can still be zero because arrays are 0-indexed. This matters because index multiplication involving zero always produces zero, and zero is divisible by every positive integer.

Several edge cases are important to consider:

• Arrays with no repeated values should return 0.
• Arrays where every value is identical may generate many candidate pairs.
• Cases where one index is 0 are special because 0 * j = 0, which is always divisible by k.
• Very small arrays, such as length 1, cannot form any valid pair.
• Cases where k = 1 make the divisibility condition always true, reducing the problem to counting equal-value pairs.

Approaches

Brute Force Approach

The most direct solution is to examine every possible pair of indices (i, j) where i < j.

For each pair:

1. Check whether nums[i] == nums[j].
2. If they are equal, compute i * j.
3. Check whether (i * j) % k == 0.
4. If both conditions are satisfied, increment the answer.

This approach is guaranteed to be correct because it explicitly checks every possible pair against the problem conditions.

Although brute force is often too slow for large inputs, the constraints here are very small. With n <= 100, the total number of pairs is at most:

$$\frac{100 \times 99}{2} = 4950$$

This is easily manageable.

Key Insight

The key observation is that the constraints are small enough that a quadratic solution is already optimal in practice.

We do not need advanced optimizations such as grouping indices by value or using number theory tricks because the straightforward pair-checking approach is simple, readable, and efficient enough.

The only real optimization is to avoid unnecessary work by first checking whether the values are equal before performing the divisibility calculation.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every pair directly
Optimal	O(n²)	O(1)	Same as brute force because constraints are very small

Algorithm Walkthrough

Step by Step Algorithm

1. Initialize a variable count to 0.

This variable will store the number of valid pairs. 2. Iterate through all possible first indices i.

The loop runs from 0 to n - 1. 3. For each i, iterate through all valid second indices j.

Since the problem requires i < j, the second loop starts at i + 1. 4. Check whether the values are equal.

If nums[i] != nums[j], the pair cannot be valid, so we skip it immediately. 5. If the values are equal, compute the index product divisibility condition.

Check whether:

$$(i \times j) \bmod k = 0$$ 6. If both conditions are satisfied, increment count. 7. After all pairs have been processed, return count.

Why it works

The algorithm examines every possible pair of indices exactly once. For each pair, it directly verifies the two required conditions from the problem statement:

• Equal values
• Divisibility of the index product

Since every valid pair is counted and no invalid pair is counted, the algorithm always produces the correct result.

Python Solution

from typing import List

class Solution:
    def countPairs(self, nums: List[int], k: int) -> int:
        n = len(nums)
        count = 0

        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

The implementation begins by storing the array length in n and initializing the answer variable count.

The outer loop selects the first index i, while the inner loop selects the second index j. Starting the inner loop at i + 1 guarantees that every pair satisfies i < j and prevents duplicate checks.

Inside the nested loops, the code first checks whether the array values are equal. Only if this condition is true does it evaluate the divisibility condition. This keeps the logic concise and efficient.

Whenever both conditions are satisfied, the answer counter is incremented. After all pairs have been checked, the final count is returned.

Go Solution

func countPairs(nums []int, k int) int {
    n := len(nums)
    count := 0

    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if nums[i] == nums[j] && (i*j)%k == 0 {
                count++
            }
        }
    }

    return count
}

The Go implementation follows the exact same logic as the Python version.

Go uses explicit integer types and standard for loops instead of Python's range. Since the constraints are very small, integer overflow is not a concern because the maximum possible product is 99 * 99 = 9801.

Slices in Go naturally handle dynamic array access, so no additional handling is needed for empty or small inputs.

Worked Examples

Example 1

Input:

nums = [3,1,2,2,2,1,3]
k = 2

We examine all pairs.

i	j	nums[i]	nums[j]	Equal?	i * j	Divisible by 2?	Count
0	1	3	1	No	0	Yes	0
0	6	3	3	Yes	0	Yes	1
1	5	1	1	Yes	5	No	1
2	3	2	2	Yes	6	Yes	2
2	4	2	2	Yes	8	Yes	3
3	4	2	2	Yes	12	Yes	4

Final answer:

4

Example 2

Input:

nums = [1,2,3,4]
k = 1

Since all numbers are distinct, there are no equal-value pairs.

i	j	nums[i]	nums[j]	Equal?
0	1	1	2	No
0	2	1	3	No
0	3	1	4	No
1	2	2	3	No
1	3	2	4	No
2	3	3	4	No

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Every pair of indices is checked once
Space	O(1)	Only a few variables are used

The algorithm uses two nested loops over the array indices. In the worst case, it checks all possible pairs, resulting in quadratic time complexity.

No additional data structures proportional to the input size are used, so the space complexity remains constant.

Test Cases

from typing import List

class Solution:
    def countPairs(self, nums: List[int], k: int) -> int:
        n = len(nums)
        count = 0

        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

solution = Solution()

assert solution.countPairs([3,1,2,2,2,1,3], 2) == 4  # provided example
assert solution.countPairs([1,2,3,4], 1) == 0  # no duplicates
assert solution.countPairs([1], 1) == 0  # single element array
assert solution.countPairs([5,5], 1) == 1  # simplest valid pair
assert solution.countPairs([5,5], 2) == 0  # equal values but product not divisible
assert solution.countPairs([7,7,7], 1) == 3  # all pairs valid
assert solution.countPairs([7,7,7], 2) == 2  # some pairs invalid
assert solution.countPairs([1,1,1,1], 3) == 1  # only one valid divisible pair
assert solution.countPairs([2,2,2,2,2], 4) == 5  # multiple valid combinations
assert solution.countPairs([1,2,1,2,1], 2) == 3  # mixed repeated values

Test Case Summary

Test	Why
[3,1,2,2,2,1,3], k=2	Validates the official example
[1,2,3,4], k=1	Ensures no duplicates returns zero
[1], k=1	Tests smallest possible array
[5,5], k=1	Tests simplest valid pair
[5,5], k=2	Tests divisibility rejection
[7,7,7], k=1	Tests all pairs valid
[7,7,7], k=2	Tests selective divisibility
[1,1,1,1], k=3	Tests sparse valid pairs
[2,2,2,2,2], k=4	Tests many repeated values
[1,2,1,2,1], k=2	Tests multiple repeated groups

Edge Cases

Single Element Array

If the array contains only one element, there are no possible pairs because a pair requires two distinct indices. A naive implementation that does not properly handle loop bounds could accidentally attempt invalid accesses. The implementation avoids this naturally because the inner loop starts at i + 1, which immediately becomes out of range.

No Repeated Values

Arrays with all unique values should always return 0, regardless of k. A buggy implementation might incorrectly count pairs based only on divisibility without verifying equality first. The solution explicitly checks nums[i] == nums[j] before incrementing the answer.

Index Zero Participation

Because the array is 0-indexed, any pair involving index 0 produces a product of 0. Since 0 is divisible by every positive integer, these pairs are always valid if the values are equal. This is an easy detail to overlook. The implementation handles it correctly because it uses the mathematical condition directly:

(i * j) % k == 0

When i is 0, the expression becomes 0 % k, which correctly evaluates to 0.

Large Number of Duplicate Values

If many elements are identical, the number of candidate pairs grows quickly. Some implementations may accidentally double count pairs or include invalid (j, i) orderings. The solution prevents this by enforcing j > i, ensuring each pair is counted exactly once.