algoadvance

Leetcode 2176. Count Equal and Divisible Pairs in an Array

Problem Statement

Given a 0-indexed integer array nums of size n and an integer k, return the number of pairs (i, j) where 0 <= i < j < n, such that:

1. nums[i] == nums[j] and
2. (i * j) is divisible by k.

Clarifying Questions

1. What is the range of the input values?
   • The constraints are 1 <= nums.length <= 100 and 1 <= nums[i] <= 100.
2. Can there be negative values or zeros in the array?
   • No, since the constraints specify 1 <= nums[i] <= 100, all elements are positive integers.
3. Is it possible for k to be zero?
   • No, according to general mathematical constraints, a divisor cannot be zero. So k >= 1.

Strategy

1. Brute Force Approach
   • Iterate over each pair (i, j) with i < j and check both conditions.
   • If both conditions are met, count it as a valid pair.
2. Optimized Approach
   • We can still use a nested loop due to the constraint nums.length <= 100, which makes it feasible.
   • For each pair (i, j), check if nums[i] == nums[j] and (i * j) % k == 0.

Code

public class Solution {
    public int countPairs(int[] nums, int k) {
        int count = 0;
        int n = nums.length;
        
        // Iterate over each pair (i, j)
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Check if nums[i] == nums[j] and (i * j) % k == 0
                if (nums[i] == nums[j] && (i * j) % k == 0) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

Time Complexity

• Iterations: The outer loop runs n times and the inner loop runs approximately n/2 times, leading to O(n^2).
• Comparison and Modulus Operations: Each pair comparison is O(1), making the total complexity O(n^2).

This is efficient given the constraints, as n is at most 100, making it computationally feasible to use O(n^2) approach.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?