Problem Informations

• Problem Index: 2176
• Problem Link: Count Equal and Divisible Pairs in an Array
• Topics: Array

Problem Description

Given a 0-indexed integer array nums of length $n$ and an integer $k$, return the number of pairs $(i, j)$ where $0 \leq i < j < n$, such that $\text{nums}[i] == \text{nums}[j]$ and $(i \times j)$ is divisible by $k$.

Example 1:

Input: nums = [3,1,2,2,2,1,3], k = 2
Output: 4
Explanation:
There are 4 pairs that meet all the requirements:
- nums[0] == nums[6], and 0 * 6 = 0, which is divisible by 2.
- nums[2] == nums[3], and 2 * 3 = 6, which is divisible by 2.
- nums[2] == nums[4], and 2 * 4 = 8, which is divisible by 2.
- nums[3] == nums[4], and 3 * 4 = 12, which is divisible by 2.

Example 2:

Input: nums = [1,2,3,4], k = 1
Output: 0
Explanation: Since no value in nums is repeated, there are no pairs (i, j) that meet all the requirements.

Constraints:

• $1 \leq \text{nums.length} \leq 100$
• $1 \leq \text{nums}[i], k \leq 100$

Intuition

The problem involves finding pairs of indices $(i, j)$ in an array such that the values at these indices are equal and the product $i \times j$ is divisible by a given integer $k$. The constraints given imply a brute force approach may be feasible. The simplest method is to iterate through all possible pairs of indices, check the conditions, and count those that satisfy both conditions. This approach is straightforward given the problem’s constraints and the requirement for equality and divisibility checks.

Approach

The algorithm employs a nested loop approach to explore every possible pair of indices $(i, j)$ where $i < j$. Here’s a step-by-step breakdown:

1. Initialization: Start by initializing a counter count to zero. This counter will accumulate the number of valid pairs that satisfy both conditions required by the problem.

2. Outer Loop: Iterate over each index i from $0$ to $n-2$ (inclusive), where $n$ is the length of the array nums. The outer loop serves to fix the first element of the potential pair.

3. Inner Loop: For each fixed index i, iterate over each index j from $i+1$ to $n-1$ (inclusive). This inner loop pairs the fixed element nums[i] with all subsequent elements nums[j], ensuring $i < j$.

4. Condition Check:

   • Equality Check: Verify if the elements at the current pair of indices are equal, i.e., nums[i] == nums[j].
   • Divisibility Check: Check if the product of the indices $i \times j$ is divisible by $k$, i.e., $(i \times j) % k == 0$.

5. Counting: If both conditions are satisfied for a particular pair $(i, j)$, increment the count by one.

6. Result: After all pairs have been examined, return the count as the total number of valid pairs found.

This approach operates using a time complexity of $O(n^2)$ due to the nested loops iterating through all pairs. Given the constraints are relatively small (with $n$ up to 100), this method performs efficiently within the provided limits. The direct checking of the required conditions for each pair ensures that the algorithm correctly identifies all eligible pairs.

Code

C++

class Solution {
public:
    int countPairs(vector<int>& nums, int k) {
        int count = 0; // Initialize the counter for pairs

        // Loop through each element and find pairs
        for (int i = 0; i < nums.size() - 1; i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                // Check if the current pair (i, j) meets the conditions
                if (i * j % k == 0 && nums[i] == nums[j]) {
                    count++; // Increment count if conditions are satisfied
                }
            }
        }

        return count; // Return the total count of valid pairs
    }
};

Python

class Solution:
    def countPairs(self, nums, k):
        count = 0  # Initialize the counter for pairs

        # Loop through each element and find pairs
        for i in range(len(nums) - 1):
            for j in range(i + 1, len(nums)):
                # Check if the current pair (i, j) meets the conditions
                if i * j % k == 0 and nums[i] == nums[j]:
                    count += 1  # Increment count if conditions are satisfied

        return count  # Return the total count of valid pairs

Complexity

• Time complexity: The time complexity of the given algorithm is $O(n^2)$. This is because there are two nested loops: the outer loop iterates over the elements of nums from index $0$ to $n-2$, and the inner loop iterates from index $i+1$ to $n-1$. Thus, the total number of iterations is the sum of the first $n-1$ integers, which is $\frac{(n-1)n}{2}$, simplifying to $O(n^2)$ in big-O notation.

• Space complexity: The space complexity of the algorithm is $O(1)$. The algorithm uses a constant amount of extra space, i.e., a single integer count to store the number of valid pairs. The input list nums and the integer $k$ are given as input parameters and do not count towards the space complexity of the algorithm itself.