Count of pairs between two arrays such that the sums are distinct
Given two arrays a[] and b[], the task is to find the count of all pairs (a[i], b[j]) such that a[i] + b[j] is unique among all the pairs i.e. if two pairs have equal sum then only one will be counted in the result.
Examples:
Input: a[] = {3, 3}, b[] = {3}
Output: 1
The two possible pairs are (a[0], b[0]) and (a[1], b[0]).
Pair 1: 3 + 3 = 6
Pair 2: 3 + 3 = 6
Input: a[] = {12, 2, 7}, b[] = {4, 3, 8}
Output: 7
Approach: Initialise count = 0 and run two loops to consider all possible pairs and store the sum of every pair in an unordered_set to check whether the sum has been obtained before. If it has then ignore the current pair else increment the count.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the count // of pairs with distinct sum int countPairs( int a[], int b[], int n, int m) { // To store the required count int cnt = 0; // Set to store the sum // obtained for each pair unordered_set< int > s; for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { // Sum of the current pair int sum = a[i] + b[j]; // If the sum obtained is distinct if (s.count(sum) == 0) { // Increment the count cnt++; // Insert sum in the set s.insert(sum); } } } return cnt; } // Driver code int main() { int a[] = { 12, 2, 7 }; int n = sizeof (a) / sizeof (a[0]); int b[] = { 4, 3, 8 }; int m = sizeof (b) / sizeof (b[0]); cout << countPairs(a, b, n, m); return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { // Function to return the count // of pairs with distinct sum static int countPairs( int a[], int b[], int n, int m) { // To store the required count int cnt = 0 ; // Set to store the sum // obtained for each pair HashSet<Integer> s = new HashSet<Integer>(); for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < m; j++) { // Sum of the current pair int sum = a[i] + b[j]; // If the sum obtained is distinct if (s.contains(sum) == false ) { // Increment the count cnt++; // Insert sum in the set s.add(sum); } } } return cnt; } // Driver code static public void main (String args[]) { int a[] = { 12 , 2 , 7 }; int n = a.length; int b[] = { 4 , 3 , 8 }; int m = b.length; System.out.println(countPairs(a, b, n, m)); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach # Function to return the count # of pairs with distinct sum def countPairs(a, b, n, m): # To store the required count cnt = 0 # Set to store the sum # obtained for each pair s = dict () for i in range (n): for j in range (m): # Sum of the current pair sum = a[i] + b[j] # If the sum obtained is distinct if ( sum not in s.keys()): # Increment the count cnt + = 1 # Insert sum in the set s[ sum ] = 1 return cnt # Driver code a = [ 12 , 2 , 7 ] n = len (a) b = [ 4 , 3 , 8 ] m = len (b) print (countPairs(a, b, n, m)) # This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // Function to return the count // of pairs with distinct sum static int countPairs( int []a, int []b, int n, int m) { // To store the required count int cnt = 0; // Set to store the sum // obtained for each pair HashSet< int > s = new HashSet< int >(); for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { // Sum of the current pair int sum = a[i] + b[j]; // If the sum obtained is distinct if (s.Contains(sum) == false ) { // Increment the count cnt++; // Insert sum in the set s.Add(sum); } } } return cnt; } // Driver code static public void Main (String []args) { int []a = { 12, 2, 7 }; int n = a.Length; int []b = { 4, 3, 8 }; int m = b.Length; Console.WriteLine(countPairs(a, b, n, m)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript implementation of the approach // Function to return the count // of pairs with distinct sum function countPairs(a, b, n, m) { // To store the required count let cnt = 0; // Set to store the sum // obtained for each pair let s = new Set(); for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { // Sum of the current pair let sum = a[i] + b[j]; // If the sum obtained is distinct if (s.has(sum) == false ) { // Increment the count cnt++; // Insert sum in the set s.add(sum); } } } return cnt; } // Driver code let a = [ 12, 2, 7 ]; let n = a.length; let b = [ 4, 3, 8 ]; let m = b.length; document.write(countPairs(a, b, n, m)); // This code is contributed by susmitakundugoaldanga. </script> |
7
Time complexity: O(N * M).
Auxiliary Space: O(1).