For example, if the input integer array is {2, 6, 3, 9, 11} and given sum is 9, the output should be {6,3}.
The first solution which comes in my mind is our friend brute-force, naive but genuine. You take one number from the array and then loop through array and output pairs which is equal to given sum. You do this for all numbers in 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 : 7Integer 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 : 7Integer 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 hash table. So total complexity of the solution would be O(N). Here is a Java program which 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 addif(!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) 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 which doesn't require additional space, also known as in-place solution. If 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' 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 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 set of constraints that only unique pair needs to be printed even if array contains duplicated and find bugs on these solution.
Source: Java67
The Tech Platform
Commentaires