Given an array of integers, and a number ‘sum’, print all pairs in the array whose sum is equal to ‘sum’.
Examples :
Input : arr[] = {1, 5, 7, -1, 5},
sum = 6
Output : (1, 5) (7, -1) (1, 5)
Input : arr[] = {2, 5, 17, -1},
sum = 7
Output : (2, 5)
A simple solution is to traverse each element and check if there’s another number in the array which can be added to it to give sum.
C++
#include <bits/stdc++.h>
using namespace std;
int printPairs(int arr[], int n, int sum)
{
int count = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] + arr[j] == sum)
cout << "(" << arr[i] << ", " << arr[j]
<< ")" << endl;
}
int main()
{
int arr[] = { 1, 5, 7, -1, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int sum = 6;
printPairs(arr, n, sum);
return 0;
}
|
Java
class GFG {
static void printPairs(int arr[], int n, int sum)
{
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] + arr[j] == sum)
System.out.println("(" + arr[i] + ", "
+ arr[j] + ")");
}
public static void main(String[] arg)
{
int arr[] = { 1, 5, 7, -1, 5 };
int n = arr.length;
int sum = 6;
printPairs(arr, n, sum);
}
}
|
Python3
def printPairs(arr, n, sum):
for i in range(0, n):
for j in range(i + 1, n):
if (arr[i] + arr[j] == sum):
print("(", arr[i],
", ", arr[j],
")", sep="")
arr = [1, 5, 7, -1, 5]
n = len(arr)
sum = 6
printPairs(arr, n, sum)
|
C#
using System;
class GFG {
static void printPairs(int[] arr, int n, int sum)
{
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] + arr[j] == sum)
Console.Write("(" + arr[i] + ", "
+ arr[j] + ")"
+ "\n");
}
public static void Main()
{
int[] arr = { 1, 5, 7, -1, 5 };
int n = arr.Length;
int sum = 6;
printPairs(arr, n, sum);
}
}
|
Javascript
<script>
function printPairs(arr, n, sum)
{
let count = 0;
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++)
if (arr[i] + arr[j] == sum)
document.write("(" + arr[i] + ", "
+ arr[j] + ")" + "<br>");
}
let arr = [ 1, 5, 7, -1, 5 ];
let n = arr.length;
let sum = 6;
printPairs(arr, n, sum);
</script>
|
PHP
<?php
function printPairs($arr, $n, $sum)
{
$count = 0;
for ($i = 0; $i < $n; $i++)
for ( $j = $i + 1; $j < $n; $j++)
if ($arr[$i] + $arr[$j] == $sum)
echo "(", $arr[$i], ", ",
$arr[$j], ")", "\n";
}
$arr = array (1, 5, 7, -1, 5);
$n = sizeof($arr);
$sum = 6;
printPairs($arr, $n, $sum);
?>
|
Output
(1, 5)
(1, 5)
(7, -1)
Time Complexity: O(N^2) where N is the number of elements.
Auxiliary Space: O(1)
Method 2 (Use hashing).
We create an empty hash table. Now we traverse through the array and check for pairs in the hash table. If a matching element is found, we print the pair number of times equal to the number of occurrences of the matching element.
Note that the worst case of time complexity of this solution is O(c + n) where c is the count of pairs with a given sum.
C++
#include <bits/stdc++.h>
using namespace std;
void printPairs(int arr[], int n, int sum)
{
unordered_map<int, int> m;
for (int i = 0; i < n; i++) {
int rem = sum - arr[i];
if (m.find(rem) != m.end()) {
int count = m[rem];
for (int j = 0; j < count; j++)
cout << "(" << rem << ", " << arr[i] << ")"
<< endl;
}
m[arr[i]]++;
}
}
int main()
{
int arr[] = { 1, 5, 7, -1, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int sum = 6;
printPairs(arr, n, sum);
return 0;
}
|
Java
import java.util.*;
class GFG {
static void printPairs(int arr[], int n, int sum)
{
HashMap<Integer, Integer> mp
= new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++) {
int rem = sum - arr[i];
if (mp.containsKey(rem)) {
int count = mp.get(rem);
for (int j = 0; j < count; j++)
System.out.print("(" + rem + ", "
+ arr[i] + ")"
+ "\n");
}
if (mp.containsKey(arr[i])) {
mp.put(arr[i], mp.get(arr[i]) + 1);
}
else {
mp.put(arr[i], 1);
}
}
}
public static void main(String[] args)
{
int arr[] = { 1, 5, 7, -1, 5 };
int n = arr.length;
int sum = 6;
printPairs(arr, n, sum);
}
}
|
Python3
def printPairs(arr, n, sum):
mydict = dict()
for i in range(n):
temp = sum - arr[i]
if temp in mydict:
count = mydict[temp]
for j in range(count):
print("(", temp, ", ", arr[i],
")", sep="", end='\n')
if arr[i] in mydict:
mydict[arr[i]] += 1
else:
mydict[arr[i]] = 1
if __name__ == '__main__':
arr = [1, 5, 7, -1, 5]
n = len(arr)
sum = 6
printPairs(arr, n, sum)
|
C#
using System;
using System.Collections;
using System.Collections.Generic;
class GFG {
static void printPairs(int[] arr, int n, int sum)
{
Dictionary<int, int> m = new Dictionary<int, int>();
for (int i = 0; i < n; i++) {
int rem = sum - arr[i];
if (m.ContainsKey(rem)) {
int count = m[rem];
for (int j = 0; j < count; j++) {
Console.Write("(" + rem + ", " + arr[i]
+ ")"
+ "\n");
}
}
if (m.ContainsKey(arr[i])) {
m[arr[i]]++;
}
else {
m[arr[i]] = 1;
}
}
}
public static void Main(string[] args)
{
int[] arr = { 1, 5, 7, -1, 5 };
int n = arr.Length;
int sum = 6;
printPairs(arr, n, sum);
}
}
|
Javascript
<script>
function printPairs(arr, n, sum) {
var m = {};
for (var i = 0; i < n; i++) {
var rem = sum - arr[i];
if (m.hasOwnProperty(rem)) {
var count = m[rem];
for (var j = 0; j < count; j++) {
document.write("(" + rem + ", " + arr[i] + ")" + "<br>");
}
}
if (m.hasOwnProperty(arr[i])) {
m[arr[i]]++;
} else {
m[arr[i]] = 1;
}
}
}
var arr = [1, 5, 7, -1, 5];
var n = arr.length;
var sum = 6;
printPairs(arr, n, sum);
</script>
|
Output
(1, 5)
(7, -1)
(1, 5)
Time Complexity: O(N) where N is the number of elements in array
Auxiliary Space: O(N) due to map.
Method 3.
Another method to Print all pairs with the given sum is given as follows:
STEP BY STEP APPROACH :
- Define a function pairedElements(arr, sum) that takes an array arr and a sum sum as input parameters.
- Initialize two variables low and high to 0 and len(arr) – 1 respectively.
- Start a while loop that continues as long as low is less than high.
- Inside the while loop, check if the sum of elements at indices low and high is equal to sum.
- If the sum is equal to sum, print the pair of elements at indices low and high.
- If the sum is greater than sum, decrement high by 1.
- If the sum is less than sum, increment low by 1.
- Return from the function.
- In the if __name__ == ‘__main__’: block, initialize an array arr with some integers.
- Sort the array arr in ascending order using the sort() method.
- Call the function pairedElements(arr, 6) to find pairs of elements that sum up to 6.
- The program prints the pairs of elements that sum up to 6.
C++
#include <bits/stdc++.h>
using namespace std;
void pairedElements(int arr[], int sum, int n)
{
int low = 0;
int high = n - 1;
while (low < high) {
if (arr[low] + arr[high] == sum) {
cout << "The pair is : (" << arr[low] << ", "
<< arr[high] << ")" << endl;
}
if (arr[low] + arr[high] > sum) {
high--;
}
else {
low++;
}
}
}
int main()
{
int arr[] = { 2, 3, 4, -2, 6, 8, 9, 11 };
int n = sizeof(arr) / sizeof(arr[0]);
sort(arr, arr + n);
pairedElements(arr, 6, n);
}
|
Java
import java.util.Arrays;
public class SumOfPairs {
public void pairedElements(int arr[], int sum)
{
int low = 0;
int high = arr.length - 1;
while (low < high) {
if (arr[low] + arr[high] == sum) {
System.out.println("The pair is : ("
+ arr[low] + ", "
+ arr[high] + ")");
}
if (arr[low] + arr[high] > sum) {
high--;
}
else {
low++;
}
}
}
public static void main(String[] args)
{
int arr[] = { 2, 3, 4, -2, 6, 8, 9, 11 };
Arrays.sort(arr);
SumOfPairs sp = new SumOfPairs();
sp.pairedElements(arr, 6);
}
}
|
Python3
def pairedElements(arr, sum):
low = 0
high = len(arr) - 1
while (low < high):
if (arr[low] +
arr[high] == sum):
print("The pair is : (", arr[low],
", ", arr[high], ")")
if (arr[low] + arr[high] > sum):
high -= 1
else:
low += 1
if __name__ == '__main__':
arr = [2, 3, 4, -2,
6, 8, 9, 11]
arr.sort()
pairedElements(arr, 6)
|
C#
using System;
public class SumOfPairs {
public void pairedElements(int[] arr, int sum)
{
int low = 0;
int high = arr.Length - 1;
while (low < high) {
if (arr[low] + arr[high] == sum) {
Console.WriteLine("The pair is : ("
+ arr[low] + ", "
+ arr[high] + ")");
}
if (arr[low] + arr[high] > sum) {
high--;
}
else {
low++;
}
}
}
public static void Main(String[] args)
{
int[] arr = { 2, 3, 4, -2, 6, 8, 9, 11 };
Array.Sort(arr);
SumOfPairs sp = new SumOfPairs();
sp.pairedElements(arr, 6);
}
}
|
Javascript
<script>
function pairedElements(arr, sum, n) {
var low = 0;
var high = n - 1;
while (low < high) {
if (arr[low] + arr[high] == sum) {
document.write("The pair is : (" +
arr[low] + ", " +
arr[high] + ")<br>");
}
if (arr[low] + arr[high] > sum) {
high--;
}
else {
low++;
}
}
}
var arr = [ 2, 3, 4, -2, 6, 8, 9, 11]
var n = arr.length;
arr.sort(function(a,b){return a-b;});
pairedElements(arr, 6, n);
</script>
|
Output
The pair is : (-2, 8)
The pair is : (2, 4)
Time Complexity: O(N*logN) where N is the number of elements
Auxiliary Space: O(1)
Approach: Using Hashing
Steps:
- Initialize an empty hash set.
- Traverse through the array.
- For each element in the array, check if the difference between the sum and the current element exists in the hash set. If it exists, print the pair.
- Add the current element to the hash set.
C++
#include <iostream>
#include <unordered_set>
using namespace std;
void printPairs(int arr[], int n, int sum) {
unordered_set<int> s;
for (int i = 0; i < n; i++) {
int temp = sum - arr[i];
if (s.find(temp) != s.end()) {
cout << "(" << temp << ", " << arr[i] << ")" << endl;
}
s.insert(arr[i]);
}
}
int main() {
int arr[] = {1, 5, 7, -1, 5};
int sum = 6;
int n = sizeof(arr)/sizeof(arr[0]);
printPairs(arr, n, sum);
return 0;
}
|
Java
import java.util.*;
public class Main {
public static void printPairs(int[] arr, int n, int sum) {
Set<Integer> s = new HashSet<>();
for (int i = 0; i < n; i++) {
int temp = sum - arr[i];
if (s.contains(temp)) {
System.out.println("(" + temp + ", " + arr[i] + ")");
}
s.add(arr[i]);
}
}
public static void main(String[] args) {
int[] arr = {1, 5, 7, -1, 5};
int sum = 6;
int n = arr.length;
printPairs(arr, n, sum);
}
}
|
Python3
def printPairs(arr, sum):
s = set()
for i in range(len(arr)):
temp = sum - arr[i]
if (temp in s):
print("(", temp, ",", arr[i], ")")
s.add(arr[i])
arr = [1, 5, 7, -1, 5]
sum = 6
printPairs(arr, sum)
|
C#
using System;
using System.Collections.Generic;
class Program
{
static void PrintPairs(int[] arr, int n, int sum)
{
HashSet<int> s = new HashSet<int>();
for (int i = 0; i < n; i++)
{
int temp = sum - arr[i];
if (s.Contains(temp))
{
Console.WriteLine($"({temp}, {arr[i]})");
}
s.Add(arr[i]);
}
}
static void Main(string[] args)
{
int[] arr = { 1, 5, 7, -1, 5 };
int sum = 6;
int n = arr.Length;
PrintPairs(arr, n, sum);
}
}
|
Javascript
function GFG(arr, sum) {
const set = new Set();
for (let i = 0; i < arr.length; i++) {
const temp = sum - arr[i];
if (set.has(temp)) {
console.log(`(${temp}, ${arr[i]})`);
}
set.add(arr[i]);
}
}
function main() {
const arr = [1, 5, 7, -1, 5];
const sum = 6;
GFG(arr, sum);
}
main();
|
Output
( 1 , 5 )
( 7 , -1 )
( 1 , 5 )
Time Complexity: O(n)
Auxiliary Space: O(n)
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!
