Given an array arr[] of N elements. The task is to count the total number of indices (i, j) such that arr[i] = arr[j] and i != j
Examples:
Input: arr[]={1, 2, 1, 1}
Output: 3
Explanation:
In the array arr[0]=arr[2]=arr[3]
Valid Pairs are (0, 2), (0, 3) and (2, 3)Input: arr[]={2, 2, 3, 2, 3}
Output: 4
Explanation:
In the array arr[0]=arr[1]=arr[3] and arr[2]=arr[4]
So Valid Pairs are (0, 1), (0, 3), (1, 3), (2, 4)
For the Naive and Efficient Approach please refer to the previous post of this article.
Better Approach – using Two Pointers: The idea is to sort the given array and the difference of index having the same elements. Below are the steps:
- Sort the given array.
- Initialize the two pointers left and right as 0 and 1 respectively.
- Now till right is less than N, do the following:
- If the element index left and right are the same then increment the right pointer and add the difference of right and left pointer to the final count.
- Else update the value of left to right.
- Print the value of count after the above steps.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function that counts the pair in // the array arr[] int countPairs( int arr[], int n) { int ans = 0; // Sort the array sort(arr, arr + n); // Initialize two pointers int left = 0, right = 1; while (right < n) { if (arr[left] == arr[right]) // Add all valid pairs to answer ans += right - left; else left = right; right++; } // Return the answer return ans; } // Driver Code int main() { // Given array arr[] int arr[] = { 2, 2, 3, 2, 3 }; int N = sizeof (arr) / sizeof (arr[0]); // Function call cout << countPairs(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function that counts the pair in // the array arr[] static int countPairs( int arr[], int n) { int ans = 0 ; // Sort the array Arrays.sort(arr); // Initialize two pointers int left = 0 , right = 1 ; while (right < n) { if (arr[left] == arr[right]) // Add all valid pairs to answer ans += right - left; else left = right; right++; } // Return the answer return ans; } // Driver Code public static void main(String[] args) { // Given array arr[] int arr[] = { 2 , 2 , 3 , 2 , 3 }; int N = arr.length; // Function call System.out.print(countPairs(arr, N)); } } // This code is contributed by Rohit_ranjan |
Python3
# Python3 program for the above approach # Function that counts the pair in # the array arr[] def countPairs(arr, n): ans = 0 # Sort the array arr.sort() # Initialize two pointers left = 0 right = 1 ; while (right < n): if (arr[left] = = arr[right]): # Add all valid pairs to answer ans + = right - left; else : left = right; right + = 1 # Return the answer return ans # Driver Code if __name__ = = "__main__" : # Given array arr[] arr = [ 2 , 2 , 3 , 2 , 3 ] N = len (arr) # Function call print (countPairs(arr, N)) # This code is contributed by Chitranayal |
C#
// C# program for the above approach using System; class GFG{ // Function that counts the pair in // the array []arr static int countPairs( int []arr, int n) { int ans = 0; // Sort the array Array.Sort(arr); // Initialize two pointers int left = 0, right = 1; while (right < n) { if (arr[left] == arr[right]) // Add all valid pairs to answer ans += right - left; else left = right; right++; } // Return the answer return ans; } // Driver Code public static void Main(String[] args) { // Given array []arr int []arr = { 2, 2, 3, 2, 3 }; int N = arr.Length; // Function call Console.Write(countPairs(arr, N)); } } // This code is contributed by sapnasingh4991 |
Javascript
<script> // Javascript program for the above approach // Function that counts the pair in // the array arr[] function countPairs(arr, n) { let ans = 0; // Sort the array arr.sort( function (a, b){ return a - b}); // Initialize two pointers let left = 0, right = 1; while (right < n) { if (arr[left] == arr[right]) // Add all valid pairs to answer ans += right - left; else left = right; right++; } // Return the answer return ans; } // Given array []arr let arr = [ 2, 2, 3, 2, 3 ]; let N = arr.length; // Function call document.write(countPairs(arr, N)); </script> |
4
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Efficient Approach – using single Traversal: The idea is to use Hashing and update the count of each pair whose frequency is greater than 1. Below are the steps:
- Create a unordered_map M to store the frequency of each element in the array.
- Traverse the given array and keep updating the frequency of each element in M.
- While updating frequency in the above step if the frequency of any element is greater than 0 then count that frequency to the final count.
- Print the count of pairs after the above steps.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function that count the pairs having // same elements in the array arr[] int countPairs( int arr[], int n) { int ans = 0; // Hash map to keep track of // occurrences of elements unordered_map< int , int > count; // Traverse the array arr[] for ( int i = 0; i < n; i++) { // Check if occurrence of arr[i] > 0 // add count[arr[i]] to answer if (count[arr[i]] != 0) ans += count[arr[i]]; // Increase count of arr[i] count[arr[i]]++; } // Return the result return ans; } // Driver Code int main() { // Given array arr[] int arr[] = { 1, 2, 1, 1 }; int N = sizeof (arr) / sizeof (arr[0]); // Function call cout << countPairs(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function that count the pairs having // same elements in the array arr[] static int countPairs( int arr[], int n) { int ans = 0 ; // Hash map to keep track of // occurrences of elements HashMap<Integer, Integer> count = new HashMap<>(); // Traverse the array arr[] for ( int i = 0 ; i < n; i++) { // Check if occurrence of arr[i] > 0 // add count[arr[i]] to answer if (count.containsKey(arr[i])) { ans += count.get(arr[i]); count.put(arr[i], count.get(arr[i]) + 1 ); } else { count.put(arr[i], 1 ); } } // Return the result return ans; } // Driver Code public static void main(String[] args) { // Given array arr[] int arr[] = { 1 , 2 , 1 , 1 }; int N = arr.length; // Function call System.out.print(countPairs(arr, N)); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 program for the above approach # Function that count the pairs having # same elements in the array arr[] def countPairs(arr, n) : ans = 0 # Hash map to keep track of # occurrences of elements count = {} # Traverse the array arr[] for i in range (n) : # Check if occurrence of arr[i] > 0 # add count[arr[i]] to answer if arr[i] in count : ans + = count[arr[i]] # Increase count of arr[i] if arr[i] in count : count[arr[i]] + = 1 else : count[arr[i]] = 1 # Return the result return ans # Given array arr[] arr = [ 1 , 2 , 1 , 1 ] N = len (arr) # Function call print (countPairs(arr, N)) # This code is contributed by divyesh072019 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function that count the pairs having // same elements in the array []arr static int countPairs( int []arr, int n) { int ans = 0; // Hash map to keep track of // occurrences of elements Dictionary< int , int > count = new Dictionary< int , int >(); // Traverse the array []arr for ( int i = 0; i < n; i++) { // Check if occurrence of arr[i] > 0 // add count[arr[i]] to answer if (count.ContainsKey(arr[i])) { ans += count[arr[i]]; count[arr[i]] = count[arr[i]] + 1; } else { count.Add(arr[i], 1); } } // Return the result return ans; } // Driver Code public static void Main(String[] args) { // Given array []arr int []arr = { 1, 2, 1, 1 }; int N = arr.Length; // Function call Console.Write(countPairs(arr, N)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript program for the above approach // Function that count the pairs having // same elements in the array arr[] function countPairs(arr, n) { let ans = 0; // Hash map to keep track of // occurrences of elements let count = new Map(); // Traverse the array arr[] for (let i = 0; i < n; i++) { // Check if occurrence of arr[i] > 0 // add count[arr[i]] to answer if (count.has(arr[i])) { ans += count.get(arr[i]); count.set(arr[i], count.get(arr[i]) + 1); } else { count.set(arr[i], 1); } } // Return the result return ans; } // Driver Code let arr = [ 1, 2, 1, 1 ]; let N = arr.length; // Function call document.write(countPairs(arr, N)); // This code is contributed by avanitrachhadiya2155 </script> |
3
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!