Leetcode 2176: Count Equal and Divisible Pairs in an Array

Input: The input consists of an integer array `nums` and an integer `k`. The array represents the magic numbers found in different bags, and `k` is a divisor used to filter the valid pairs.

Example: [5, 2, 3, 5, 2, 3], k = 6

Constraints:

• 1 <= nums.length <= 100

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

Output: The output should be an integer representing the number of pairs `(i, j)` that satisfy the given conditions.

Example: 3

Constraints:

• The output must be an integer.

Goal: The goal is to find pairs `(i, j)` such that `nums[i] == nums[j]` and the product `i * j` is divisible by `k`.

Steps:

• Iterate over each element in the `nums` array.

• For each element, check previously seen indices where the value is the same and check if `i * j` is divisible by `k`.

• Count all such pairs and return the count.

Goal: The input has constraints on the length of the array and the values of the integers.

Steps:

• 1 <= nums.length <= 100

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

Assumptions:

• The array `nums` is at least of length 1.

• The values in the array `nums` and `k` are positive integers.

• Input: [5, 2, 3, 5, 2, 3], k = 6

• Explanation: In this example, the valid pairs are (0, 3), (1, 4), and (2, 5), and the count of such pairs is 3.

Approach: The approach is to iterate through the array and for each element, check if any earlier occurrence of the same value forms a valid pair with the current element.

Observations:

• We need to efficiently check the conditions for each pair `(i, j)`.

• An efficient approach would involve using a map to store previously seen values and their indices.

Steps:

• Initialize a map to track indices where each value occurs.

• Iterate through the `nums` array, checking for each value if any of its earlier occurrences form a valid pair.

• For each valid pair, check if `i * j` is divisible by `k` and update the count accordingly.

Empty Inputs:

• The input array will not be empty due to the problem's constraints.

Large Inputs:

• The solution should efficiently handle arrays up to length 100.

Special Values:

• Consider the case when no value repeats in the array.

Constraints:

• Ensure that the solution works within the input constraints.

int countPairs(vector<int>& nums, int k) {
    unordered_map<int,vector<int>> umap;
    int count = 0;
    for(int i = 0; i < nums.size(); i++) 
    {
        if(umap.find(nums[i]) != umap.end()) 
        {
            for(auto x : umap[nums[i]]) 
                if((i * x) % k == 0)
                    count++;
        }
        
        umap[nums[i]].push_back(i);
    }
    return count;
}

1 : Function Definition

int countPairs(vector<int>& nums, int k) {

Define the function `countPairs` that takes a vector of integers `nums` and an integer `k`, and returns an integer `count` representing the number of valid pairs (i, j).

2 : Data Structure Initialization

    unordered_map<int,vector<int>> umap;

Initialize an unordered map `umap` where the key is an integer from `nums`, and the value is a vector of integers that stores indices where that number appears in `nums`.

3 : Variable Initialization

    int count = 0;

Initialize a variable `count` to 0, which will keep track of the number of valid pairs that meet the condition `(i * j) % k == 0`.

4 : Loop Start

    for(int i = 0; i < nums.size(); i++)

Start a for loop to iterate through each index `i` of the `nums` vector.

5 : Condition Check

        if(umap.find(nums[i]) != umap.end())

Check if the current element `nums[i]` exists in the unordered map `umap`. If it does, proceed to find the pairs.

6 : Inner Loop Start

            for(auto x : umap[nums[i]])

Iterate through all the indices `x` where `nums[i]` has appeared earlier (from the unordered map `umap`).

7 : Pair Validation

                if((i * x) % k == 0)

For each index `x`, check if the product of the current index `i` and `x` is divisible by `k`. If it is, it's a valid pair.

8 : Count Update

                    count++;

Increment the `count` variable for each valid pair found.

9 : Map Update

        umap[nums[i]].push_back(i);

Add the current index `i` to the list of indices for `nums[i]` in the unordered map `umap`.

10 : Return Result

    return count;

Return the final count of valid pairs.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n^2)

Description: The time complexity is O(n) on average, but in the worst case (when many elements are the same), it could reach O(n^2).

Best Case: O(1)

Worst Case: O(n)

Description: The space complexity is O(n) due to the map storing indices for each element in the array.

Leetcode 2176: Count Equal and Divisible Pairs in an Array

Explore →