[Array] Count Equal and Divisible Pairs in an Array - Easy

Counting equal and divisible pairs in an array is a simple problem. It needs us to find pairs of elements that are the same and where one element can divide the other. We can solve this problem in different ways. We can use brute force methods or better solutions with data structures like HashMaps. We want to count the valid pairs in the array efficiently.

In this article, we will look at counting equal and divisible pairs closely. First, we will understand the problem statement. After that, we will talk about the brute force method to solve this in Java. Next, we will look at a better solution using HashMaps in Java. We will also show a Python version of the same idea, using collections and list comprehensions. Then, we will give a C++ solution and show how to use the Standard Template Library (STL) well. Finally, we will compare the different methods and answer common questions about this topic.

  • [Array] Count Equal and Divisible Pairs in an Array - Easy Tutorial
  • Understanding the Problem Statement for Count Equal and Divisible Pairs
  • Brute Force Approach to Count Equal and Divisible Pairs in Java
  • Optimized Approach Using HashMap in Java
  • Python Implementation of Count Equal and Divisible Pairs
  • Using Collections and List Comprehensions in Python
  • C++ Solution for Counting Equal and Divisible Pairs
  • Efficient Use of STL for Counting in C++
  • Comparative Analysis of Different Approaches
  • Frequently Asked Questions

For more reading on related topics, we can find these articles helpful: Array Two Sum - Easy, Array Contains Duplicate - Easy, and Array Maximum Subarray - Easy.

Understanding the Problem Statement for Count Equal and Divisible Pairs

We want to count equal and divisible pairs in an array. We need to find pairs of indices ((i, j)) that follow these rules:

  1. The elements at these indices are the same: ( [i] = [j] )
  2. The index ( j ) is bigger than ( i ): ( j > i )
  3. The element at index ( j ) can be divided by the element at index ( i ): ( [j] [i] = 0 )

Input and Output

  • Input: We have an array of integers.
  • Output: We need to give the count of pairs that meet the rules above.

Example

Let’s look at an example with the array ([1, 2, 1, 4, 2]):

  • The valid pairs are:
    • ( (0, 2) ): ( [0] = 1 ), ( [2] = 1 )
    • ( (1, 4) ): ( [1] = 2 ), ( [4] = 2 ) and ( 2 = 0 )

So, we can say the output for this example is (2).

Constraints

  • The size of the array can be big, so using a brute-force method may not work well.
  • We should think about time and space complexity when we make a solution.

This problem is useful in data analysis. It helps us find connections between elements based on specific rules.

Brute Force Approach to Count Equal and Divisible Pairs in Java

We can use a brute force method to count equal and divisible pairs in an array. This means we check each possible pair of elements. For each pair, we see if the elements are equal or if one can divide the other. This way of doing things takes time of (O(n^2)), where (n) is the size of the array.

Implementation

Here is a simple code in Java:

public class CountPairs {
    public static int countEqualAndDivisiblePairs(int[] arr) {
        int count = 0;
        int n = arr.length;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr[i] == arr[j] || (arr[j] != 0 && arr[i] % arr[j] == 0)) {
                    count++;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 2, 2};
        int result = countEqualAndDivisiblePairs(array);
        System.out.println("Count of Equal and Divisible Pairs: " + result);
    }
}

Explanation

  • Outer Loop: This goes through each element in the array.
  • Inner Loop: This compares the current element with all the next elements.
  • Condition Check:
    • First, it checks if the two elements are equal.
    • Then, it checks if the first element can be divided by the second one. We make sure the second element is not zero to avoid division by zero.

Example

For the input array {1, 2, 3, 4, 2, 2}: - Pairs counted: - (2, 2) are equal. - (4, 2) since 4 can be divided by 2.

The output will be Count of Equal and Divisible Pairs: 4.

This brute force way is easy to understand. But it can be slow for larger arrays because it takes a lot of time. If we want better speed, we can look for better methods like using a HashMap.

Optimized Approach Using HashMap in Java

To count equal and divisible pairs in an array, we can use a HashMap. It helps us store how many times each number appears. This way is much faster than using the brute force method.

Steps:

  1. Initialize a HashMap: This will keep each number in the array as a key. The value will be how many times that number appears.
  2. Iterate through the array: For each number, we will find out how many pairs we can make. We check both conditions: equal and divisible.
  3. Count pairs: For each unique number, we will see how many pairs we can make based on how many times it appears.

Java Implementation:

import java.util.HashMap;

public class CountPairs {
    public static int countEqualAndDivisiblePairs(int[] arr) {
        HashMap<Integer, Integer> frequencyMap = new HashMap<>();
        int count = 0;

        // Store frequency of each number
        for (int num : arr) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // Calculate pairs
        for (int key : frequencyMap.keySet()) {
            int freq = frequencyMap.get(key);
            // Count pairs (nC2) for equal elements
            count += (freq * (freq - 1)) / 2;

            // Count pairs with divisibility
            for (int otherKey : frequencyMap.keySet()) {
                if (key != otherKey && otherKey % key == 0) {
                    count += freq * frequencyMap.get(otherKey);
                }
            }
        }

        return count;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 4, 4, 4};
        System.out.println("Count of equal and divisible pairs: " + countEqualAndDivisiblePairs(arr));
    }
}

Explanation of the Code:

  • The countEqualAndDivisiblePairs method starts a HashMap to keep track of how many times each element appears.
  • It goes through the array to fill the HashMap.
  • After that, it counts pairs. First, it counts pairs of equal numbers. Then, it checks if the unique numbers can divide each other.
  • Finally, we return the total count.

This method makes the process faster and reduces the time to about O(n^2) in the worst case. The HashMap helps us count frequencies easily.

Python Implementation of Count Equal and Divisible Pairs

We can count equal and divisible pairs in an array using Python. One simple way is to use a nested loop. This is easy to understand but may not be the best for large data sets. Here is the Python code:

def count_equal_and_divisible_pairs(arr, k):
    count = 0
    n = len(arr)

    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] == arr[j] and arr[i] % k == 0:
                count += 1
                
    return count

# Example usage
arr = [3, 6, 3, 9, 12]
k = 3
result = count_equal_and_divisible_pairs(arr, k)
print("Count of equal and divisible pairs:", result)

In this function: - arr is the input array. - k is the number we check for divisibility. - The function goes through each pair of indices (i, j) where i is less than j. It checks if the elements are equal and if they can be divided by k.

If we want to make it faster, we can use a dictionary. This way, we store how many times each number that can be divided by k appears. This will help us a lot:

def optimized_count_equal_and_divisible_pairs(arr, k):
    frequency = {}
    count = 0

    for num in arr:
        if num % k == 0:
            if num in frequency:
                count += frequency[num]
                frequency[num] += 1
            else:
                frequency[num] = 1
                
    return count

# Example usage
arr = [3, 6, 3, 9, 12]
k = 3
result = optimized_count_equal_and_divisible_pairs(arr, k)
print("Count of equal and divisible pairs:", result)

In this better version: - We use a dictionary to track how many times each number that can divide by k appears. - For each number, if it is already in the dictionary, we add the current count to our total count of pairs.

This method works better for big arrays. If you want to learn more, you can look at other array problems like Array Contains Duplicate or Array Maximum Subarray.

Using Collections and List Comprehensions in Python

In Python, we can use collections and list comprehensions to count equal and divisible pairs in an array. This way lets us solve the problem in a simple and effective method.

Implementation Using Collections

To count pairs of indices ( (i, j) ) where ( i < j ), the values are equal ( A[i] = A[j] ), and ( A[j] ) is divisible by ( A[i] ), we can use the Counter class from the collections module.

from collections import Counter

def count_equal_divisible_pairs(arr):
    count = 0
    freq = Counter(arr)

    for num in freq:
        if num == 0:  # We skip zero to avoid division by zero
            continue
        # Here we calculate pairs where A[j] is divisible by A[i]
        for key in freq:
            if key % num == 0:
                count += freq[num] * freq[key]  # We count pairs
    return count

# Example usage
arr = [1, 2, 2, 4]
result = count_equal_divisible_pairs(arr)
print(result)  # Output: 5

List Comprehensions for a Compact Solution

We can also use list comprehensions to count pairs. This way filters and counts valid pairs directly. Here is how we can do it:

def count_equal_divisible_pairs(arr):
    return sum(1 for i in range(len(arr)) for j in range(i + 1, len(arr))
               if arr[i] == arr[j] and arr[j] % arr[i] == 0)

# Example usage
arr = [1, 2, 2, 4]
result = count_equal_divisible_pairs(arr)
print(result)  # Output: 5

This method checks all pairs and looks at the conditions. It uses Python’s clear syntax to keep things easy to read and understand.

Using collections and list comprehensions in Python helps us make our solution clear and also follows Python’s style. This makes our code better and easier to work with.

C++ Solution for Counting Equal and Divisible Pairs

We can count equal and divisible pairs in an array using C++. We will use a simple method that goes through the array to find pairs that meet the conditions.

Implementation

Here is a C++ solution that counts the number of pairs (i, j) where arr[i] == arr[j], i < j, and also checks if arr[i] is divisible by arr[j] or the other way around.

#include <iostream>
#include <vector>

using namespace std;

int countEqualAndDivisiblePairs(const vector<int>& arr) {
    int count = 0;
    int n = arr.size();

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] == arr[j] && (arr[i] % arr[j] == 0 || arr[j] % arr[i] == 0)) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    vector<int> arr = {1, 2, 2, 4, 4, 8};
    int result = countEqualAndDivisiblePairs(arr);
    cout << "Count of equal and divisible pairs: " << result << endl;
    return 0;
}

Explanation

  • Function Definition: The function countEqualAndDivisiblePairs takes a list of integers as input.
  • Nested Loops: We use a nested loop to check each pair of indices (i, j) where i < j.
  • Condition Check: The if statement checks if the numbers are equal and if one is divisible by the other.
  • Count Variable: Each time we find a valid pair, we increase the count.
  • Output: We print the result in the main function.

Complexity

  • Time Complexity: O(n^2) because of the nested loops.
  • Space Complexity: O(1) since we use a fixed amount of space.

This C++ code shows well how to count equal and divisible pairs in an array. It meets the problem needs. For more information on array work and related problems, we can look at Array Remove Duplicates from Sorted Array.

Efficient Use of STL for Counting in C++

In C++, we can use the Standard Template Library (STL) to count equal and divisible pairs in an array. STL helps us solve the problem easier and faster.

Steps to Implement

  1. Count Frequencies: We will use a std::unordered_map to keep track of how many times each element appears in the array.
  2. Count Divisible Pairs: Next, we will go through the array. For each element, we will check how many pairs we can make based on its frequency and divisibility.

Code Implementation

Here is a simple code example in C++:

#include <iostream>
#include <unordered_map>
#include <vector>

int countPairs(std::vector<int>& nums) {
    std::unordered_map<int, int> freqMap;
    int pairCount = 0;

    // Count frequencies of each number
    for (int num : nums) {
        freqMap[num]++;
    }

    // Count pairs
    for (auto& [num, count] : freqMap) {
        for (auto& [otherNum, otherCount] : freqMap) {
            if (num != otherNum && num % otherNum == 0) {
                pairCount += count * otherCount;
            }
        }
    }

    return pairCount;
}

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 6};
    std::cout << "Count of equal and divisible pairs: " << countPairs(nums) << std::endl;
    return 0;
}

Explanation of Code

  • Frequency Map: The unordered_map freqMap holds each number and how many times it appears.
  • Nested Iteration: The first loop goes through each unique number. The second loop looks for pairs that fit the divisibility rule.
  • Count Calculation: If we find a divisible pair, we add the product of their frequencies to the total pair count.

Benefits of Using STL

  • Efficiency: It helps us avoid using too many nested loops. This makes our code run faster.
  • Simplicity: The code is easier to read and manage.
  • Flexibility: It can work with different data types and conditions easily.

Using STL in C++ to count equal and divisible pairs in an array helps us make the solution better and faster.

Comparative Analysis of Different Approaches

When we solve the problem of counting equal and divisible pairs in an array, we can use different methods. Each method has its own pros and cons, especially in time complexity and how easy it is to use. Here, we will look at the brute force method and the optimized method using HashMap in Java. We will also see how to do this in Python and C++.

Brute Force Approach

The brute force way uses two loops. Each loop checks every pair of elements in the array. This method has a time complexity of O(n^2).

public int countEqualDivisiblePairs(int[] nums) {
    int count = 0;
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] == nums[j] || (nums[i] % nums[j] == 0) || (nums[j] % nums[i] == 0)) {
                count++;
            }
        }
    }
    return count;
}

Optimized Approach Using HashMap

The HashMap method is better. It lowers the time complexity to O(n) by keeping track of counts of elements. Then we check pairs based on their counts. This works much better for larger arrays.

public int countEqualDivisiblePairs(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    int count = 0;
    
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
    
    for (int num : map.keySet()) {
        int freq = map.get(num);
        count += (freq * (freq - 1)) / 2; // Count equal pairs
        for (int key : map.keySet()) {
            if (num != key && (num % key == 0 || key % num == 0)) {
                count += freq * map.get(key); // Count divisible pairs
            }
        }
    }
    
    return count;
}

Python Implementation

In Python, we use dictionaries. The logic is similar to the HashMap method in Java.

def count_equal_divisible_pairs(nums):
    count = 0
    freq_map = {}
    
    for num in nums:
        freq_map[num] = freq_map.get(num, 0) + 1
    
    for num, freq in freq_map.items():
        count += (freq * (freq - 1)) // 2  # Equal pairs
        for key, key_freq in freq_map.items():
            if num != key and (num % key == 0 or key % num == 0):
                count += freq * key_freq  # Divisible pairs
    
    return count

C++ Solution

The C++ version also uses unordered_map for speed.

#include <unordered_map>
#include <vector>
using namespace std;

int countEqualDivisiblePairs(vector<int>& nums) {
    unordered_map<int, int> freq_map;
    int count = 0;

    for (int num : nums) {
        freq_map[num]++;
    }

    for (auto& [num, freq] : freq_map) {
        count += (freq * (freq - 1)) / 2; // Equal pairs
        for (auto& [key, key_freq] : freq_map) {
            if (num != key && (num % key == 0 || key % num == 0)) {
                count += freq * key_freq; // Divisible pairs
            }
        }
    }

    return count;
}

Performance Comparison

  • Brute Force: O(n^2) time complexity. It is easy to use but slow for large arrays.
  • HashMap/Dictionary: O(n) time complexity. It is much faster by counting frequencies.
  • Language Performance: All methods are similar in logic. But speed can change based on how each language works and what data structure we use.

This analysis shows that using a HashMap is better than brute force methods for counting equal and divisible pairs in an array. This knowledge helps us choose the right method based on our needs and the input size.

For more insights on array problems, check out Array Two Sum - Easy and Array Contains Duplicate - Easy.

Frequently Asked Questions

1. What is the problem of counting equal and divisible pairs in an array?

Counting equal and divisible pairs in an array means we find pairs of indices (i, j). Here, array[i] is equal to array[j] and i is not the same as j. Also, array[i] must divide array[j] without any remainder. This problem is common in coding challenges. It can help us understand how to work with arrays and count pairs better.

2. How can I optimize counting equal and divisible pairs in Java?

To make counting equal and divisible pairs faster in Java, we can use a HashMap. This helps us keep track of how many times each number appears in the array. With this, we can get counts quickly and check for divisibility fast. This method works better than a simple brute-force way, especially when we have big data sets.

3. Is there a Python implementation for counting equal and divisible pairs?

Yes, we can count equal and divisible pairs in Python. We can use list comprehensions and the collections module. By using Python’s built-in tools, we can make a solution that is simple and quick. Using a dictionary to count can also help us make the code even faster.

4. What are common approaches to solve the equal and divisible pairs problem in C++?

In C++, we can use the Standard Template Library (STL) to solve the equal and divisible pairs problem well. Data structures like unordered_map let us look up and count quickly. By combining STL algorithms and data structures, we can make our solution better. It will be more elegant and faster.

5. How does the brute force approach compare to optimized methods for this problem?

The brute force approach for counting equal and divisible pairs uses nested loops. This gives us a time complexity of O(n²). This is not good for big arrays. On the other hand, optimized methods with hash maps can reduce the complexity to O(n). This makes them better for programs that need speed. We need to understand these differences for good coding practices.

Feel free to look at related ideas and problems, like Array Two Sum or Finding the Majority Element. This will help us learn more about arrays and how to make them work better.