Takes an array arr, a number value and size of the array as input and returns an array of two numbers that add up to value. In case there is more than one pair in the array containing numbers that add up to value, you are required to return only one such pair. If no such pair found then simply return the array.
Input
An array, value, and size of the array
Output
An array with two integers that add up to value
Sample Input
arr = [1,21,3,14,5,60,7,6]
value = 81
Sample Output
arr = [21,60]
For example, in this illustration, we are given 81 as the number value and when we traverse the whole array we find that 21 and 60 are the integers that add up to 81.
Solution #1: Brute Force
int * findSum(int arr[], int value, int size) {
//if sum is greater than given value => Pointer 2 to Left.
int * result = new int[2];
for (int i=0; i<size; i++) {
for (int j=i+1; j<size; j++) {
if (arr[i]+arr[j] == value) {
result[0] = arr[i];
result[1] = arr[j];
return result; // containing 2 number
}
}
}
return arr;
}
int main(){
int size = 5, value = 9;
int arr[size] = {2,4,5,7,8};
if(size > 0){
int * arr2 = findSum(arr, value, size);
int num1 = arr2[0];
int num2 = arr2[1];
if((num1 + num2) != value)
cout << "Not Found" << endl;
else {
cout << "Number 1 = " << num1 << endl;
cout << "Number 2 = " << num2 << endl;
cout << "Sum = " << num1+num2 << endl;
}
} else {
cout << "Input Array is Empty!" << endl;
}
}This is the most time-intensive but intuitive solution. Traverse the whole array of the given size for each element in the array and check if any of the two elements add up to the given number value. So, use a nested for-loop and iterate over the entire array for each element.
Time Complexity
Solution #2: Sorting the array
//Helper Function to sort given Array (Quick Sort)
int partition(int arr[], int low, int high){
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j=low; j<high; j++){
// If current element is <= to pivot
if (arr[j] <= pivot) {
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
void sort(int arr[], int low, int high){
if (low < high){
int pi = partition(arr, low, high);
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}
//Return 2 elements of arr that sum to the given value
int * findSum(int arr[], int value, int size) {
//Helper sort function that uses the Quicksort Algorithm
sort(arr, 0, size - 1); //Sort the array in Ascending Order
int Pointer1 = 0; //Pointer 1 -> At Start
int Pointer2 = size - 1; //Pointer 2 -> At End
int * result = new int[2];
int sum = 0;
while (Pointer1 != Pointer2) {
sum = arr[Pointer1] + arr[Pointer2]; //Calulate Sum of Pointer 1 and 2
if (sum < value)
Pointer1++; //if sum is less than given value => Move Pointer 1 to Right
else if (sum > value)
Pointer2--;
else {
result[0] = arr[Pointer1];
result[1] = arr[Pointer2];
return result; // containing 2 number
}
}
return arr;
}
int main(){
int size = 5, value = 9;
int arr[size] = {2,4,5,7,8};
if(size > 0){
int * arr2 = findSum(arr, value, size);
int num1 = arr2[0];
int num2 = arr2[1];
if((num1 + num2) != value)
cout << "Not Found" << endl;
else {
cout << "Number 1 = " << num1 << endl;
cout << "Number 2 = " << num2 << endl;
cout << "Sum = " << num1+num2 << endl;
}
} else {
cout << "Input Array is Empty!" << endl;
}
}While solution #1 is very intuitive, it is not very time efficient. A better way to solve this is by first sorting the array, then using two variables, one starting from the first index of the array and second from size-1 index of the array. If the sum of the elements on these indexes of the array is smaller than given value then increment index from the start else decrement index from the end, until the given value is not equal to the sum. Store the elements on these indexes in result array and return it.
Time Complexity
Solution #3: Using Hashing
int * findSum(int arr[], int value, int size) {
//if sum is greater than given value => Pointer 2 to Left.
int * result = new int[2];
unordered_map<int, int> mp;
for (int i=0; i<size; i++) {
mp[arr[i]]++;
}
for(int i=0; i<size; i++){
if(mp[abs(arr[i]-value)] > 0){
result[0] = arr[i];
result[1] = abs(arr[i]-value);
}
}
return result;
}
int main(){
int size = 5, value = 9;
int arr[size] = {2,4,5,7,8};
if(size > 0){
int * arr2 = findSum(arr, value, size);
int num1 = arr2[0];
int num2 = arr2[1];
if((num1 + num2) != value)
cout << "Not Found" << endl;
else {
cout << "Number 1 = " << num1 << endl;
cout << "Number 2 = " << num2 << endl;
cout << "Sum = " << num1+num2 << endl;
}
} else {
cout << "Input Array is Empty!" << endl;
}
}In solution we are using a hash table to solve this problem. This is the most optimized solution for this problem.