We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Equal and Divisible Pairs in an Array

Number: 2277

Difficulty: Easy

Paid? No

Companies: zeta suite

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 <= i < j < n such that nums[i] == nums[j] and (i * j) is divisible by k.

Key Insights

  • Only consider pairs where the numbers are equal.
  • Check if the product of the indices i and j is divisible by k.
  • Since n is small (n <= 100), a brute force approach with nested loops is feasible.
  • An alternative approach is to group identical numbers and then only check pairs within each group.

Space and Time Complexity

Time Complexity: O(n^2) in the worst-case scenario
Space Complexity: O(n) due to the additional data structure used for grouping

Solution

We use a grouping strategy to map each unique number to a list of its indices. For each group of indices, we iterate over all pairs (i, j) such that i < j, and then we check if the product of these indices is divisible by k. This approach reduces unnecessary comparisons by focusing only on indices that need to be paired (those with equal values).

Code Solutions

def count_pairs(nums, k):
    # Create a dictionary to map each number to its list of indices
    num_to_indices = {}
    for i, num in enumerate(nums):
        if num in num_to_indices:
            num_to_indices[num].append(i)
        else:
            num_to_indices[num] = [i]
    
    count = 0
    # For each group of indices with the same number, check pair combinations
    for indices in num_to_indices.values():
        for i in range(len(indices)):
            for j in range(i + 1, len(indices)):
                # Check if the product of indices is divisible by k
                if (indices[i] * indices[j]) % k == 0:
                    count += 1
    return count

# Example usage
print(count_pairs([3,1,2,2,2,1,3], 2))  # Expected Output: 4
← Back to All Questions