Count Equal and Divisible Pairs in an Array

EASY

Description

Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs (i, j) where 0 <= i < j < n, 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:
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 <= nums.length <= 100
1 <= nums[i], k <= 100

Approaches

Checkout 2 different approaches to solve Count Equal and Divisible Pairs in an Array. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

The most straightforward approach is to use brute force. We can iterate through every possible pair of indices (i, j) in the array such that i < j. For each pair, we check if it satisfies the two conditions given in the problem: nums[i] == nums[j] and (i * j) % k == 0. If both conditions hold true, we increment a counter.

Algorithm

Initialize a counter count to 0.
Use a nested loop to iterate through all pairs of indices (i, j) such that 0 <= i < j < n.
For each pair, check if nums[i] == nums[j].
If the values are equal, check if the product of indices (i * j) is divisible by k.
If both conditions are met, increment the count.
After iterating through all pairs, return count.

We initialize a counter variable, count, to zero. We then use a nested loop structure. The outer loop iterates with index i from 0 to n-2, and the inner loop iterates with index j from i + 1 to n-1, where n is the length of the array. This structure ensures that we only consider pairs (i, j) with i < j. Inside the inner loop, we check if nums[i] is equal to nums[j] and if the product (i * j) is divisible by k. If both conditions are met, we increment our count. After the loops complete, the count holds the total number of valid pairs.

class Solution {
    public int countPairs(int[] nums, int k) {
        int n = nums.length;
        int count = 0;
        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;
    }
}

Complexity Analysis

Time Complexity: O(n^2), where `n` is the number of elements in `nums`. The nested loops iterate through all possible pairs `(i, j)` with `i < j`, resulting in approximately `n^2 / 2` comparisons.Space Complexity: O(1), as we only use a few variables to store the count and loop indices, not dependent on the input size.

Pros and Cons

Pros:

Very simple to understand and implement.
Requires no additional memory, making its space complexity optimal.

Cons:

Inefficient for large input sizes as it checks every possible pair of indices, regardless of their values.
Performs many unnecessary comparisons when the array contains many unique values.

Code Solutions

Checking out 3 solutions in different languages for Count Equal and Divisible Pairs in an Array. Click on different languages to view the code.

class Solution {
public
  int countPairs(int[] nums, int k) {
    int n = nums.length;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        if (nums[i] == nums[j] && (i * j) % k == 0) {
          ++ans;
        }
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Count Equal and Divisible Pairs in an Array

Data Structures:

Array

Companies:

zeta suite |