Monday, September 11, 2023

How to Find all Pairs in Array of Integers Whose sum is Equal to a Given Number in Java? Solution Example

Practicing coding problems are very important to do well in any programming interview. You should at your best on data structures like an array, linked list, and string to clear any programming interview and believe me, you can not do this in one day or one week. It's rather a long process of learning through coding, and that's where these small coding problems help. Today, we are going to look at another interesting programming question from the array; write a program to find all pairs of integers whose sum is equal to a given number. For example, if the input integer array is {2, 6, 3, 9, 11} and the given sum is 9, the output should be {6,3}.

Sounds simple? maybe, but this exact question has appeared in a technical interview at Amazon, Microsoft, Facebook, and a couple of other Fortune five tech companies in the past. Many of you might already hear about this question and some of you may already know the solution to this problem as well, but it's not enough to know just the answer.

In a programming interview, many things matter apart from the correct solution. For example, the first thing the Interviewer looks at is whether a candidate can ask the right questions or not. So before jumping straight to coding, spare a second or two to think about the problem and clear any doubt you may have.

For example, you can ask the following questions based upon the problem statement given above :
  • Does the array contain only positive or negative numbers?
  • What if the same pair repeats twice, should we print it every time?
  • Is the reverse of the pair is acceptable e.g. can we print both (4,1) and (1,4) if the given sum is 5.
  • Do we need to print only a distinct pair? does (3, 3) is a valid pair forgiven sum of 6?
  • How big the array is?
Many programmers are afraid to ask questions instead they like to assume about it, but during coding interviews IMHO it's always better to ask questions. First, it shows that you have not mugged the answer and second it demonstrates that you have the ability to think through a problem, which is a very important quality of any professional programmer.

Now let's go back to the question, for simplicity we can assume that we just need to print a pair of integers once or twice depending upon their occurrence, but the pair has to be distinct, (2,2) or (3, 3) is not valid pair.




3 Solutions to Find Pair Of Integers in Array whose Sum is Given Number

The first solution which comes to my mind is our friend brute-force, naive but genuine. You take one number from the array and then loop through an array and output pairs which are equal to a given sum. You do this for all numbers in the first array, as shown in the following Java program :

1. Brute Force Solution


import java.util.Arrays;

/**
 * Java Program to find pairs on integer array whose sum is equal to k
 * 
 * @author WINDOWS 8
 */
public class ProblemInArray{

    public static void main(String args[]) {
        int[] numbers = { 2, 4, 3, 5, 7, 8, 9 };
        int[] numbersWithDuplicates = { 2, 4, 3, 5, 6, -2, 4, 7, 8, 9 };
        prettyPrint(numbers, 7);
        prettyPrint(numbersWithDuplicates, 7);
    }

    /**
     * Prints all pair of integer values from given array whose sum is 
     * is equal to given number.
     * complexity of this solution is O(n^2)
     */
    public static void printPairs(int[] array, int sum) {

        for (int i = 0; i < array.length; i++) {
            int first = array[i];
            for (int j = i + 1; j < array.length; j++) {
                int second = array[j];

                if ((first + second) == sum) {
                    System.out.printf("(%d, %d) %n", first, second);
                }
            }

        }
    }
    /**
     * Utility method to print input and output for better explanation.
     */
    public static void prettyPrint(int[] givenArray, int givenSum){
        System.out.println("Given array : " + Arrays.toString(givenArray));
        System.out.println("Given sum : " + givenSum);
        System.out.println("Integer numbers, whose sum is equal to value : "
                                + givenSum);
        printPairs(givenArray, givenSum);
    }

}

Output:
Given sum : 7
Integer numbers, whose sum is equal to value : 7
(2, 5) 
(4, 3) 
Given array : [2, 4, 3, 5, 6, -2, 4, 7, 8, 9]
Given sum : 7
Integer numbers, whose sum is equal to value : 7
(2, 5) 
(4, 3) 
(3, 4) 
(-2, 9) 

This solution is correct but its time complexity is very hight, O(n^2), which means the Interviewer will surely ask you to improve your answer and come up with a solution whose complexity is either O(1), O(n) or O(nLog(n)). So let's dig deeper to improve this answer. In order to find two numbers in an array whose sum equals a given value, we probably don't need to compare each number with other.

What we can do here is to store all numbers in a hashtable and just check if it contains second value in a pair. For example, if a given sum is 4 and one number in pair is 3, then other must be 1 or -7. Do you remember the first question we asked, if array only contains positive numbers then we don't need to check for negative values in Map. How is this solution better than previous one? It would require less comparisons.

Only N to iterate through array and insert values in a Set because add() and contains() both O(1) operation in the hash table. So total complexity of the solution would be O(N). Here is a Java program that find the pair of values in the array whose sum is equal to k using Hashtable or Set. 

In this program we have also written a utility method to generate random numbers in a given range in Java. You can use this method for testing with random inputs.

By the way, random numbers are only good for demonstration, don't use them in your unit test. One more good thing you can learn from printPairsUsingSet() method is pre validation, checking if inputs are valid to proceed further.

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * Java Program to find two elements in an array that sum to k.
 * 
 * @author WINDOWS 8
 */
public class ArraySumUsingSet {

    public static void main(String args[]) {
       prettyPrint(getRandomArray(9), 11);
       prettyPrint(getRandomArray(10), 12);
    }

    /**
     * Given an array of integers finds two elements in the array 
     * whose sum is equal to n.
     * @param numbers
     * @param n
     */
    public static void printPairsUsingSet(int[] numbers, int n){
        if(numbers.length < 2){
            return;
        }        
        Set set = new HashSet(numbers.length);
        
        for(int value : numbers){
            int target = n - value;
            
            // if target number is not in set then add
            if(!set.contains(target)){
                set.add(value);
            }else {
                System.out.printf("(%d, %d) %n", value, target);
            }
        }
    }
    
    /*
     * Utility method to find two elements in an array that sum to k.
     */
    public static void prettyPrint(int[] random, int k){
        System.out.println("Random Integer array : " + Arrays.toString(random));
        System.out.println("Sum : " + k);
        System.out.println("pair of numbers from an array whose sum equals "
                                     + k);
        printPairsUsingSet(random, k);
    }
    
    /**
     * Utility method to return random array of Integers in a range of 0 to 15
     */
    public static int[] getRandomArray(int length){
        int[] randoms = new int[length];
        for(int i=0; i<length; i++){
            randoms[i] = (int) (Math.random()*15);
        }
        return randoms;
    }

}

Output:
Random Integer array : [0, 14, 0, 4, 7, 8, 3, 5, 7]
Sum : 11
pair of numbers from an array whose sum equals 11
(7, 4) 
(3, 8) 
(7, 4) 
Random Integer array : [10, 9, 5, 9, 0, 10, 2, 10, 1, 9]
Sum : 12
pair of numbers from an array whose sum equals 12
(2, 10) 

How to find two integers in Java array whose sum equal to given number


One more thing, here we are using HashSet but since HashSet in Java internally uses HashMap, it would not make any difference if use either of those data structure.By the this solution has few constraints, first it would need additional space of order O(n) to store numbers in Hashtable or Set, so you need additional space which could be problem if array is very large (remember the question we asked before writing solution).

For a large array, you need a solution that doesn't require additional space, also known as in-place solution. If the interviewer will ask you how do you find if two values in an array sum to a given value without any additional space, first solution will also not work because it's complexity is too high and it would too long to sort a large array. A solution with complexity e.g. O(n), O(logN) or O(NLongN) should work though.

A more efficient in-place solution would be to sort the array and use two pointers to scan through array from both direction i.e. beginning and end. If sum of both the values are equal to given number then we output the pair and advance them. If the sum of two numbers is less than k then we increase the left pointer, else if the sum is greater than k we decrement the right pointer, until both pointers meet at some part of the array.

The complexity of this solution would be O(NlogN) due to sorting. Remember to use a in-place sorting algorithm like quicksort to sort the array as we don't have additional space. Thankfully, Arrays.sort() method uses a two pivot quicksort algorithm to sort array of primitives.

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * Java Program to find all pairs on integer array whose sum is equal to k
 * 
 * @author WINDOWS 7
 */
public class PrintArrayPairs {

    public static void main(String args[]) {
       prettyPrint( new int[]{ 12, 14, 17, 15, 19, 20, -11}, 9);
       prettyPrint( new int[]{ 2, 4, 7, 5, 9, 10, -1}, 9);
    }

    /**
     * Given a number finds two numbers from an array so that
     * the sum is equal to that number k.
     * @param numbers
     * @param k
     */
    public static void printPairsUsingTwoPointers(int[] numbers, int k){
        if(numbers.length < 2){
            return;
        }
        Arrays.sort(numbers);
        
        int left = 0; int right = numbers.length -1;
        while(left < right){
            int sum = numbers[left] + numbers[right];
            if(sum == k){
                System.out.printf("(%d, %d) %n", numbers[left],
                                    numbers[right]);
                left = left + 1;
                right = right -1;
                
            }else if(sum < k){
                left = left +1;
                
            }else if (sum > k) {
                right = right -1;
            }
        }
       
    }
    
    /*
     * Utility method to print two elements in an array that sum to k.
     */
    public static void prettyPrint(int[] random, int k){
        System.out.println("input int array : " + Arrays.toString(random));
        System.out.println("All pairs in an array of integers 
                          whose sum is equal to a given value " + k);
        printPairsUsingTwoPointers(random, k);
    }
    
}

Output :
input int array : [12, 14, 17, 15, 19, 20, -11]
All pairs in an array of integers whose sum is equal to a given value 9
(-11, 20) 
input int array : [2, 4, 7, 5, 9, 10, -1]
All pairs in an array of integers whose sum is equal to a given value 9
(-1, 10) 
(2, 7) 
(4, 5) 


That's all on this array based interview question to find all pairs in an array of integers whose sum is equal to a given integer. We have seen three ways to solve this problem starting from the simplest brute-force solution to acceptable O(N) with additional space and O(NLogN) in place.

If anyone like to do some more practice, I would suggest writing JUnit test cases for this problem, given a set of constraints that only a unique pair needs to be printed even if array contains duplicated and find bugs on these solutions.

Alternatively, you can also try to solve its cousin question, given an array of integers check whether there are 3 numbers that sum up to 0 or a given number. Remember more fun is in the journey than reaching the destination :)

Related Data Structure and Algorithm Interview Questions from Javarevisited Blog
  • Difference between array and linked list data structure? (answer)
  • Difference between a binary tree and binary search tree? (answer)
  • How to reverse a linked list in Java using iteration and recursion? (solution)
  • How to reverse an array in place in Java? (solution)
  • How to find all permutations of a String in Java? (solution)
  • How to reverse a String in place in Java? (solution)
  • How to remove duplicate elements from an array without using Collections? (solution)
  • Top 5 Books on Data Structure and Algorithms for Java Developers (books)
  • Top 5 books on Programming/Coding Interviews (list)

Exercises : 

1) Write JUnit tests for this problem and check if each of these solutions passes those tests.
2) Come up with a better solution in terms of time and space complexity?
3) Find boundary conditions on which this solution breaks.

33 comments :

Unknown said...

Hi,

In a solution involving HashSet where if a target number is not in the set it is added to it you are checking if a set contains a number with contains but if I read correctly the .add method returns false if the object you are adding is already in the set so this piece of code:

if(!set.contains(target))
{
set.add(value);
}

could be written like this:

if(set.add(value))

correct? :)

SARAL SAXENA said...

well javin I think we can also go for the below solution having these constraints in my mind ..

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class FindPairs {
public static void main(String args[]) {
Integer[] numbers = { 2, 4, 3, 5, 7, 8, 9 };
int sum = 7;
List Numbers = Arrays.asList(numbers);
Collections.sort(Numbers);
for (int i : Numbers) {
if (Numbers.contains(sum - i) && i <= (sum / 2) && i != (sum - i)) {
System.out.print((sum - i) + " & ");
System.out.println(+i);
}
}
}
}

The condition i<=(sum/2) is required to prevent double repetition of pairs (2 & 5) and (5 & 2). The condition i!=(sum-i) is required to prevent same number in paring. (For example, if your sum is 8, then if you don't use this condition, you will also get pair (4,4) ).

5 & 2

4 & 3

Unknown said...

A perfect number is one that is the sum of its factors, excluding itself. The 1st perfect number is 6 because 6 = 1 + 2 + 3. The 2nd perfect number is 28 which equals 1 + 2 + 4 + 7 + 14. The third is 496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248. In each case, the number is the sum of all its factors excluding itself.

Write a method named henry that takes two integer arguments, i and j and returns the sum of the ith and jth perfect numbers. So for example, henry (1, 3) should return 502 because 6 is the 1st perfect number and 496 is the 3rd perfect number and 6 + 496 = 502.

The function signature is
int henry (int i, int j)

You do not have to worry about integer overflow, i.e., you may assume that each sum that you have to compute can be represented as a 31 bit integer. Hint: use modulo arithmetic to determine if one number is a factor of another.

Anonymous said...

In the section when you explain the Hash method, the example is wrong:
" For example, if given sum is 4 and one number in pair is 3, then other must be 1 or -7."
The other can't be -7, otherwise the sum is -4 not 4.

Anonymous said...

Yeah bad example
I think what he meant is that
If negative numbers are allowed
If sum is 1 and one number is 3 other number has to be -2 this logic needs to be handled based on what interviewer says

Pritam_Ghosh said...

How to find sum of array in fibonacci series?Suppose arr={2,6,3,1}=31
like 2+6=8,8+3=11,11+1=12
now sum of 8+11+12=31???Program i got in Sach test

Unknown said...

thks

NindoDeveloper said...

private static void printUniquePairsUsingHashtable(int[] array, int sum) {
HashSet hashSet = new HashSet<>();
for (int firstNumInPair : array) {
int secondNumInPair = sum - firstNumInPair;
if (!hashSet.contains(secondNumInPair)) {
if (!hashSet.add(firstNumInPair))
hashSet.add(secondNumInPair);
} else {
if (!hashSet.contains(firstNumInPair))
System.out.printf("(%d, %d)%n", firstNumInPair, secondNumInPair);
}
}
}

Anonymous said...

public static void main(String[] args) {
int a[] = {5,3,4,8};
pairSum(a,9);
}

private static void pairSum(int[] a,int sum) {
Arrays.sort(a);
System.out.println(Arrays.toString(a));
int i=0;
int j=0;
int temp=a[0];
for( i=0,j=(a.length-1);i<j;){
temp= a[i]+a[j];
if(temp==sum){
System.out.println(a[i]+" , "+ a[j]);
return;
}else if(temp<sum){
i++;
}else {
j--;
}
}

}

Anonymous said...

Hi Javin,
It seems that the 3rd method only works in the case when first set of pairs, after sorting, produces the desired sum.
In your case, e.g.
-11,20( array 1)
-1,10 ( array 2)

because then only the left and right index have proceeded further in your case.

Can you check the same program, for below set of arrays and desired sum = 8.
int[] ar = {12,3,5,1,4,6,9,10,15,-8,-1,-4,-6,-3,5,7};
after sorting ar[] becomes:
-8,-6,-4,-3,-1,1,3,4,5,5,6,7,9,10,12,15

The output should be:
(5, 3)
(-1, 9)
(-4, 12)
(5, 3)
(7, 1)

But, if you run the program for the same above provided array, you won't get any output.

Anji said...

This is so interesting and helpful for me a lot..thanks JAVA revisited..

RAJESH KUMAR said...

import java.util.HashMap;
import java.util.Map;
public class SumEqualToPairOfNumber {
public static void main(String[] args) {
int[] arr = {1, 2, 1, 3, 6, 4, 2, 2, 3};
int x = 5;
Map result = findPairs(arr, x);
for (Map.Entry entry : result.entrySet())
{
System.out.println("(" + entry.getKey() + "," + entry.getValue() +")");
}
}
public static Map findPairs(int[] arr, int a) {
int n = arr.length;
Map map = new HashMap();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] + arr[j] == a) {
map.put(i, j);
}
}
}
return map;
}
}

Unknown said...

finding all pairs of elements with a given difference in an array of integers in java

Anonymous said...

This code only considers 2 numbers for forming the pairs. I am not very good at coding, but I guess this code will consider all pairs.


public static String sum_pairs(int[] array, int number)
{
String result = "";
int sum = 0;
int j = 0;
String temp = "";

for(int i = 0; i < array.length; i ++)
{
sum += array[i];
j = i + 1;
temp += array[i] + ",";
while(sum < number)
{
if(j == array.length - 1)
{
break;
}
if(j != i && sum + array[j] <= number)
{
if(j != array.length -1 )
{ int k = j + 1;
while(k < array.length - 1)
{
if(array[k] == number - sum)
{
sum += array[k];
temp += array[k] + ",";
}
k ++;
}
}
if(sum < number)
{
sum += array[j];
temp += array[j] + ",";
}
}
j ++;
}
if(j != i && sum == number)
{
result += temp + "\n";
}
temp = "";
sum = 0;
}

return result;
}

Unknown said...

In the Method 2 : take input as {2,1,5,7} sum =8 .... it gives only {1,7} ...even though there are 2 outputs possible i,e {1,7} and {2,1,5}

Pankaj Doharey said...

Not only is it simple, it is super simple in ruby or clojure :

In ruby : [2, 6, 3, 9, 11].combination(2).select{|i| i.sum == 9}
In clojure : (filter #(= (reduce + %) 5) (combo/combinations '(1 2 3 4 5) 2))

Anonymous said...

In third case, sorting will take O(nlogn ) and while loop will take o(n) time then in combination o(nlogn) +o(n) it should be o(n). But answer states O(nlogn). Please provide your thoughts on this.

Unknown said...

Give 5 pairs of integers whose product is less than zero and whose sum is -26.

Unknown said...

Using the integers -1, 4, 40, and -25, create as many equations you can with an answer of 34. You can use each integer only once.

Anonymous said...

A = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

for i in range(len(A)-1):
for j in range(i+1, len(A)):
if A[i] + A[j] == 7:
print i, j

Unknown said...

public static void main(String[] args) {
int[] numbers = {2, 4, 3, 5, 6, -2, 4, 7, 8, 9};
int sumNumber = 7;

Arrays.sort(numbers);

for (int i = 0; i < numbers.length; i++) {
int num1 = numbers[i];
for (int j = i; j < numbers.length; j++) {
int num2 = numbers[j];
if(num1 + num2 == sumNumber) {
System.out.println("Pair : "+num1 +" "+ num2);
}else if(num1 + num2 > sumNumber) {
break;
}
}
}
}

Unknown said...

I wnt this in python can i get?

Arjun said...

public class Sum{
public static void main(String[] as){
int[] v={2,6,3,9,11};
int m=9;
for(int i=0;i<5;i++){
for(int j=i+1;j<5;j++){
if(v[i]+v[j]==m){
System.out.println("["+v[i]+" "+v[j]+"]");
}
}
}


}
}

Prakash said...

#!python3.7

#Function to print pairs
def print_pairs_matching_sum(arr, n, s):
mdict = {}
for i in arr:
if i not in mdict:
mdict[i] = s - i
if (s-i) in mdict:
print(mdict[i], i)


#Test Driving Code
a = [2, 4, 5, 1, 3, 2, 3, 4]
print_pairs_matching_sum(a, len(a), 6)

javin paul said...

Python is like cheat-code for coding, makes it so simple and succinct.

Unknown said...

Yes set returns false if we try insert duplicate.
NOT operator should be removed from if.
Also try to code it to find the optimal result.

Unknown said...

public static void main(String args[]) {
int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int toplam = 10;

for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
if ((arr[i] + arr[j]) == toplam) {
System.out.println(arr[i]+ "+" +arr[j] + "=" + toplam);

}

}

}

}

Unknown said...

easiest answer
class pairing{
public static void main(String[] args) {
int[] array ={1,2,3,4,5,6,9};
int a= 10;
for(int i=0;i<array.length;i++){
for(int j=i+1;j<array.length;j++){
int b= array[i]+array[j];
if(a == b){
System.out.println("the corresponding pair is {"+array[i]+"," +array[j]+"}");
}
}
}
}
}

javin paul said...

Yes, but time complexity of this solution is O(n^2) which is not great, can you optimize your solution upto O(n) ?

Mitali Jain said...

If we take the example int arr[] = { 4, 5, 7, -1, 5, 1, 1 }; int sum = 6;
The hashset method does not return all possible pairs.

Anonymous said...

printPairsUsingSet------duplicate pair is printing so need to remove once found set .remove(target);

Anonymous said...

else {
System.out.println("pair:("+arr[i] +","+target+")");
set.remove(target);
}

Unknown said...

How can I write a program to found all numbers from 1 to n whose sum is equal to n.
Example:
15= 1+14,2+13,3+12,....,1+2+12,1+3+11,.....,1+2+3+4+5.

Post a Comment