Given an array of N positive integers. Count the number of pairs whose sum exists in the given array. While repeating pairs will not be counted again. And we can’t make a pair using same position element. Eg : (2, 1) and (1, 2) will be considered as only one pair. Please read all examples carefully.
Examples:
Input : arr[] = {1, 2, 3, 5, 10}
Output : 2
Explanation : Here there are two such pairs:
(1 + 2) = 3, (2 + 3) = 5.
Note : Here we can't take pair (5, 5) as
we can see 5 is not coming twice
Input : arr[] = {1, 5, 6, 4, -1, 5}
Output : 4
Explanation : (1 + 5) = 6, (1 + 4) = 5,
(5 + -1) = 4, (6 + -1) = 5
Note : Here (1, 5) comes twice will be
considered as only one pair.
Input : arr[] = {5, 5, 5, 5, 10}
Output : 1
Explanation : (5 + 5) = 10
Note : Here (5, 5) comes twice will be
considered as only one pair.
The idea is to map of pairs to find unique elements. We first store elements and their counts in a map. Then we traverse array elements, for every pair of elements (arr[i], arr[j]), we check if (arr[i] + arr[j]) exists in array. If exists, then we check if it is already counted using map of pairs. If not already counted, then we increment count.
Implementation:
C++
// C++ implementation to find count of unique pairs// whose sum exists in given array#include <bits/stdc++.h>using namespace std;// Returns number of pairs in arr[0..n-1] with// sum equal to 'sum'int getPairsCount(int arr[], int n){ // Store counts of all elements in map m // to find pair (arr[i], sum-arr[i]) // because (arr[i]) + (sum - arr[i]) = sum map<int, int> m; for (int i = 0; i < n; i++) m[arr[i]]++; // To remove duplicate items we use result map map<pair<int, int>, int> pairs; int count = 0; // Initialize result // Consider all pairs for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // If sum of current pair exists if (m[arr[i] + arr[j]] > 0 && pairs[{ arr[i], arr[j] }] == 0) { count++; } // Insert current pair both ways to avoid // duplicates. pairs[{ arr[i], arr[j] }]++; pairs[{ arr[j], arr[i] }]++; } } return count;}// Driver function to test the above functionint main(){ int arr[] = { 1, 5, 6, 4, -1, 5, 10 }; int n = sizeof(arr) / sizeof(arr[0]); cout << getPairsCount(arr, n); return 0;} |
Java
// Java implementation to find count of unique// pairs whose sum exists in given arrayimport java.io.*;import java.util.*;class GFG { public static int getPairsCount(int[] arr, int n) { // Store counts of all elements in map m // to find pair (arr[i], sum-arr[i]) // because (arr[i]) + (sum - arr[i]) = sum Map<Integer, Integer> m = new HashMap<>(); for (int i = 0; i < n; i++) { m.put(arr[i], m.getOrDefault(arr[i], 0) + 1); } // To remove duplicate items we use result map Map<Map.Entry<Integer, Integer>, Integer> pairs = new HashMap<>(); int count = 0; // Initialize result // Consider all pairs for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // If sum of current pair exists if (m.getOrDefault(arr[i] + arr[j], 0) > 0 && !pairs.containsKey( Map.entry(arr[i], arr[j]))) { count++; } // Insert current pair both ways to avoid // duplicates. pairs.put(Map.entry(arr[i], arr[j]), 1); pairs.put(Map.entry(arr[j], arr[i]), 1); } } return count; } public static void main(String[] args) { int[] arr = { 1, 5, 6, 4, -1, 5, 10 }; int n = arr.length; System.out.println(getPairsCount(arr, n)); }}// This code is contributed by lokesh. |
Python3
# Python3 implementation to find count # of unique pairs whose sum exists in# given array# Returns number of pairs in arr[0..n-1] # with sum equal to 'sum'def getPairsCount(arr, n): # Store counts of all elements in map m # to find pair (arr[i], sum-arr[i]) # because (arr[i]) + (sum - arr[i]) = sum m = dict() for i in range(n): m[arr[i]] = m.get(arr[i], 0) + 1 # To remove duplicate items # we use result map pairs1 = dict() count = 0 # Initialize result for i in range(n): for j in range(i + 1, n): l = arr[i] + arr[j] tp = (arr[i], arr[j]) if l in m.keys(): if tp not in pairs1.keys(): count += 1 pairs1[(arr[i], arr[j])] = 1 pairs1[(arr[j], arr[i])] = 1 return count# Driver Codearr = [1, 5, 6, 4, -1, 5, 10]n = len(arr)print(getPairsCount(arr, n))# This code is contributed by Mohit Kumar |
C#
using System;using System.Collections.Generic;class GFG { public static int GetPairsCount(int[] arr, int n) { // Store counts of all elements in dictionary m // to find pair (arr[i], sum-arr[i]) // because (arr[i]) + (sum - arr[i]) = sum Dictionary<int, int> m = new Dictionary<int, int>(); for (int i = 0; i < n; i++) { if (!m.ContainsKey(arr[i])) { m[arr[i]] = 0; } m[arr[i]] += 1; } // To remove duplicate items we use result set HashSet<Tuple<int, int>> pairs = new HashSet<Tuple<int, int>>(); int count = 0; // Initialize result // Consider all pairs for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // If sum of current pair exists if (m.ContainsKey(arr[i] + arr[j]) && m[arr[i] + arr[j]] > 0 && !pairs.Contains(new Tuple<int, int>(arr[i], arr[j]))) { count++; } // Insert current pair both ways to avoid // duplicates. pairs.Add(new Tuple<int, int>(arr[i], arr[j])); pairs.Add(new Tuple<int, int>(arr[j], arr[i])); } } return count; } public static void Main(string[] args) { int[] arr = { 1, 5, 6, 4, -1, 5, 10 }; int n = arr.Length; Console.WriteLine(GetPairsCount(arr, n)); }} |
Javascript
// JavaScript implementation to find count of unique// pairs whose sum exists in given arrayfunction getPairsCount(arr, n) { // Store counts of all elements in object // to find pair (arr[i], sum-arr[i]) // because (arr[i]) + (sum - arr[i]) = sum let m = {}; for (let i = 0; i < n; i++) { if (m[arr[i]] === undefined) { m[arr[i]] = 1; } else { m[arr[i]]++; } } // To remove duplicate items we use result object let pairs = {}; let count = 0; // Initialize result // Consider all pairs for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { // If sum of current pair exists if (m[arr[i] + arr[j]] !== undefined && !(arr[i] in pairs && arr[j] in pairs[arr[i]])) { count++; } // Insert current pair both ways to avoid duplicates. if (!(arr[i] in pairs)) { pairs[arr[i]] = {}; } pairs[arr[i]][arr[j]] = 1; if (!(arr[j] in pairs)) { pairs[arr[j]] = {}; } pairs[arr[j]][arr[i]] = 1; } } return count;}let arr = [1, 5, 6, 4, -1, 5, 10];let n = arr.length;console.log(getPairsCount(arr, n));// this code is contributed by dnyeshwatdod |
Output
6
Time complexity: O(n^2)
Space complexity: O(n)
This article is contributed by Harshit Agrawal. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
