Consider an array arr[] with n elements where the values in the array consist of both positive values and negative values, including zero. Consider a number x. Find out whether the value x can be formed by adding any two values from the given array arr[].
Example 1
Input:
Consider the array arr[] = {8,5,1,0}
Let n = 9
Output: 8,1
Explanation: For the given array, the value n=9 can be formed by adding the array values 8 and 1 which are index positions 0,2, respectively.
Example 2
Input:
Consider the array arr[][] = {-6,0,7,-9,5,2}
Let n = 10
Output: Not Possible.
Explanation For the given array arr[], the value n=10 cannot be formed by considering any pair together.
Example 3 Input:
Consider the array arr[][] = {-1,12,28,7,6,-2}
Let n = 26
Output: 28,-2
Explanation: For the given array, the value n=26 can be formed by adding the array values 28 and -2 which are at index positions 2,5, respectively. 28 + (-2) =26
Approach 1: Using Pointers
Initially, sort the given array in ascending order and initialize two pointers such that a pointer points to the first element of the sorted array and another pointer points to the last element of the sorted array. Here comes the actual logic, if the sum of the two pointer elements’ values is greater than the required sum, then decrement the right side pointer.
If the sum of the two pointer elements is lesser than the required sum, then increment the left side pointer such that it points to the next element. Follow the same process till we find the required sum. If the two pointers point to the same element, then return 0 as the required sum cannot be obtained from the given array.
Algorithm
- Initialize the array size and take the array values into the array.
- Sort the array in increasing order. Use any sorting method to sort the array.
-
Now consider two variables - beg and end.
- Initialize beg = 0.
- Initialize end = array_size-1.
-
Traverse the entire array until the required sum is found, and use the sum of the beg, and end variables to sum the elements.
- If the sum equal to the required sum is found, then return 1.
- If the sum is greater than the required sum, then decrement the end.
- If the sum is less than the required sum, then increment the beg.
- If the required sum is not found even after traversing the entire array, then return 0.
The implementation of the approach discussed above is as follows.
C++ Code
#include <bits/stdc++.h>
using namespace std;
//arraychecker function to check the 2 values
bool arraychecker(int arr[], int array_size,int sum)
{
int beg,end;
//Sorting the array in ascending order
sort(arr, arr + array_size);
//Finding the required values to get the required sum
beg = 0;
end = array_size - 1;
while (beg < end) {
if (arr[beg] + arr[end] == sum)
return 1;
else if (arr[beg] + arr[end] < sum)
beg++;
else
end--;
}
return 0;
}
//Driver Code
int main()
{
int arr[] = { 12,28,7,6 };
int sum = 18;
int array_size = sizeof(arr) / sizeof(arr[0]);
// Calling arraychecker function
if (arraychecker(arr, array_size, sum))
cout << "Required sum can be obtained using the given array elements";
else
cout << "Required sum cannot be obtained using the given array elements";
}
Output
C# Code
using System;
class Program {
static bool arraychecker(int[] arr,int array_size, int sum)
{
int beg, end;
// Sorting array elements
sort(arr, 0, array_size - 1);
beg = 0;
end = array_size - 1;
while (beg < end)
{
if (arr[beg] + arr[end] == sum)
return true;
else if (arr[beg] + arr[end] < sum)
beg++;
else
end--;
}
return false;
}
static int fun1(int[] arr, int low, int high)
{
int i,j,t,pivot,t1;
pivot = arr[high];
i = (low - 1);
for(j = low; j <= high - 1; j++)
{
if (arr[j] <= pivot)
{
i++;
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
t1 = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = t1;
return i + 1;
}
static void sort(int[] arr, int low, int high)
{
if (low < high) {
int pi = fun1(arr, low, high);
sort(arr, low, pi - 1);
sort(arr, pi + 1, high); //Sorting elements in recursive manner
}
}
// Driver code
public static void Main()
{
int[] arr = { 12,28,7,6 };
int sum = 18;
int array_size = 4;
if (arraychecker(arr, array_size, sum))
Console.Write("Required sum can be obtained using the given array elements");
else
Console.Write("Required sum cannot be obtained using the given array elements");
}
}
Output:
Java Code
import java.util.*;
class Main {
static boolean arraychecker(int arr[],int array_size, int sum)
{
int beg, end;
// Sort the array in increasing order
Arrays.sort(arr);
beg = 0;
end = array_size - 1;
while (beg<end) {
if (arr[beg] + arr[end] == sum)
return true;
else if (arr[beg] + arr[end] < sum)
beg++;
else
end--;
}
return false;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 12,28,7,6 };
int sum = 18;
int array_size = arr.length;
// calling arraychecker function
if (arraychecker(arr, array_size, sum))
System.out.println("Required sum can be obtained using the given array elements");
else
System.out.println("Required sum cannot be obtained using the given array elements");
}
}
Output
Python Code
def arraychecker(arr, arr_size, sum):
#Sorting the array in increasing order
quickSort(arr, 0, arr_size-1)
beg = 0
end = arr_size-1
# finding the two elements to get the required sum
while beg
Output
Complexity Analysis
Time Complexity: In the worst case, it takes O(n^2) as we have used Quick Sort.
Space Complexity: It takes O(n) for merge sort.
Approach 2: Using remainders of the array elements
In this approach, from the given array of elements, we pick the elements which are less than the required sum. Now we perform a modulo operation with these numbers and the required sum. We calculate the remainders because the remainders give the required sum. Now we will calculate the remainder of these elements.
Consider the array, Arr[] = {1, 4, 45, 6, 10} Required sum = 16 From the given array pick the numbers which are less than 16. So the elements would be 1,4,6,10,-8. We need to get the remainder of these values. To get the remainders, we perform the modulo operation: So, ( 1%16 ) = 1 ( 4%16 ) = 4 ( 6%16 ) = 6 ( 10%16 ) = 10
Algorithm
1. Initialize the array with all the elements.
2. Initialize all the remaining elements to zero.
3. Now, traverse through the entire array.
If arr[i] is less than the sum: Rem = arr[i]%x // this gives the remainder for the values. Rem[r] = rem[r]+1 //it increases the count of elements if it has same remainder.
4. Now start traversing the remainder array from starting to middle
If rem[i]>0 and rem[i-1]>0: Print Yes // as we found the required pair of elements.
5. If the pair is not found in the above step, then it means that we have traversed from the start to the middle of the array. As of now, we are at the middle of the array, a. if x is even:
If rem[x/2] > 1: // if we found two elements with rem x/2 Print Yes else print No.
b. if x is odd:
If rem[x/2]>1 and rem[x-x/2]>1: //as x is odd 2, we are checking for two elements Print Yes else print No.
C++ Code
#include <iostream>
using namespace std;
//numbers function
void numbers(int arr[], int sum, int x)
{
int i;
int rem[x];
for (i = 0; i < x; i++)
{
//initializing rem with 0's
rem[i] = 0;
}
for (i = 0; i < sum; i++)
{
if (arr[i] < x)
{
rem[arr[i] % x]++;
}
}
//Traversing After reaching middle
for (i = 1; i < x / 2; i++) { if (rem[i] > 0 && rem[x - i] > 0)
{
cout << "Required sum can be obtained using the given array elements"<< "\n"; break; } } if (i >= x / 2)
{
if (x % 2 == 0)
{
if (rem[x / 2] > 1)
{
//If x is even
cout << "Required sum can be obtained using the given array elements"<< "\n";
}
else
{
cout << "Required sum cannot be obtained using the given array elements"<< "\n"; } } else { //If x is odd if (rem[x / 2] > 0 &&
rem[x - x / 2] > 0)
{
cout << "Required sum can be obtained using the given array elements"<< "\n";
}
else
{
cout << "Required sum cannot be obtained using the given array elements"<< "\n";
}
}
}
}
//Driver Code
int main()
{
int arr[] = { 12,28,7,6 };
int sum = 18;
int arr_size = sizeof(arr) / sizeof(arr[0]);
// Function calling
numbers(arr, arr_size, sum);
Output
C# Code
using System;
class program
{
static void arraychecker(int []arr, int n, int x)
{
int i;
int []rem = new int[x];
for (i = 0; i < x; i++)
{
//initializing rem with 0's
rem[i] = 0;
}
for (i = 0; i < n; i++)
{
if (arr[i] < x)
{
rem[arr[i] % x]++; // updating the count of the numbers
}
}
//Traversing the array from start to end
for (i = 1; i < x / 2; i++) { if (rem[x-i] > 0 && rem[i] > 0)
{
Console.Write("Required sum can be obtained using the given array elements");
break;
}
}
if (i >= x / 2) //At middle of the array
{
if (x % 2 == 0)
{
if (rem[x / 2] > 1)
{
Console.Write("Required sum can be obtained using the given array elements"); // if x is even
}
else
{
Console.Write("Required sum cannot be obtained using the given array elements");
}
}
else // if x is odd
{
if (rem[x / 2] > 0 && rem[x - x / 2] > 0)
{
Console.Write("Required sum can be obtained using the given array elements");
}
else
{
Console.WriteLine("Required sum cannot be obtained using the given array elements");
}
}
}
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 12,28,7,6 };
int sum = 18;
int array_size = arr.Length;
// Calling the function arraychecker
arraychecker(arr, array_size, sum);
}
}
Output
Java Code
import java.util.*;
class Main
{
static void numbers(int arr[], int sum, int x)
{
int i;
int []rem = new int[x];
//rem with all 0's
for (i = 0; i < x; i++)
{
rem[i] = 0;
}
for (i = 0; i < sum; i++)
{
if (arr[i] < x)
{
rem[arr[i] % x]++;
}
}
// finding pairs by traversing through the remainder list
for (i = 1; i < x / 2; i++) { if (rem[i] > 0 && rem[x - i] > 0)
{
System.out.print("Required sum can be obtained using the given array elements");
break;
}
}
//After reaching middle of array
if (i >= x / 2)
{
if (x % 2 == 0)
{
if (rem[x/2] > 1)
{
System.out.print("Required sum can be obtained using the given array elements");
}
else
{
System.out.print("Required sum cannot be obtained using the given array elements");
}
}
else
{
//if x is odd
if (rem[x/2] > 0 && rem[x-x/2] > 0)
{
System.out.print("Required sum can be obtained using the given array elements");
}
else
{
System.out.print("Required sum cannot be obtained using the given array elements");
}
}
}
}
//Driver Code
public static void main(String[] args)
{
int arr[] = { 12,28,7,6 };
int sum = 18;
int array_size = arr.length;
// Function calling
numbers(arr, array_size, sum);
}
}
Output
Python Code
def numbers(arr, sum, x):
rem = []
for i in range(x):
# adding 0's to rem
rem.append(0)
for i in range(sum):
if (arr[i] < x): rem[arr[i] % x] += 1 # Traversing from start to middle for i in range(1, x // 2): if (rem[i] > 0 and rem[x - i] > 0):
print("Required sum can be obtained using the given array elements")
break
#After reaching middle of array
if (i >= x // 2):
if (x % 2 == 0):
if (rem[x // 2] > 1): # if x is even
print("Required sum can be obtained using the given array elements")
else:
print("Required sum cannot be obtained using the given array elements")
else: # if x is odd
if (rem[x // 2] > 0 and rem[x - x // 2] > 0):
print("Required sum can be obtained using the given array elements")
else:
print("Required sum cannot be obtained using the given array elements")
# Driver Code
arr = [ 12,28,7,6 ]
sum = 18
arr_size = len(arr)
# calling the numbers function
numbers(arr, arr_size, sum)
Output
Complexity Analysis
Time Complexity : It takes O(n+x) time complexity.
Space Complexity : It requires only O(x) complexity.
Conclusion
In this article, we have discussed how to check if there are any pairs of numbers that sum up to a given value. The logic is discussed in two approaches, where one approach uses the concept of pointers and another approach uses a hashmap data structure. We have also discussed the algorithm, and code implementation in c++, Java, Python, and C# for both approaches. We hope this article helps you to solve this problem and its variants in a better and more efficient way.
Happy Coding!
People are also reading:
- Longest subarray with sum as K
- Find whether an array is subset of another array
- Program to Rotate an Array
- Construct a Binary Tree from Inorder and Preorder traversals
- Write a Program to read from a text file and then write in another text file
- Write a Program to convert given inches into equivalent yard, and feet
- Sort an array in one swap whose two elements are swapped
- Longest Palindromic Subsequence using Dynamic Programming
- Rearrange an array such that arr[i] = i
- Majority Element
Leave a Comment on this Post