Given an array A[] of n numbers and another number x, the task is to check whether or not there exist two elements in A[] whose sum is exactly x. Examples: Input: arr[] = {0, -1, 2, -3, 1}, x= -2Output: YesExplanation: If we calculate the sum of the output,1 + (-3) = -2Input: arr[] = {1, -2, 1, 0, 5}, x = 0Output: No
Question
Given an array A[] of n numbers and another number x, the task is to check whether or not there exist two elements in A[] whose sum is exactly x. Examples: Input: arr[] = {0, -1, 2, -3, 1}, x= -2Output: YesExplanation: If we calculate the sum of the output,1 + (-3) = -2Input: arr[] = {1, -2, 1, 0, 5}, x = 0Output: No
Solution
To solve this problem, you can use a technique called hashing. Here are the steps:
- Initialize an empty hash table s.
- Do the following for each element A[i] in A[]. a. If s[x - A[i]] is set then print the pair (A[i], x - A[i]) b. Insert A[i] into s.
Let's take the first example:
Input: arr[] = {0, -1, 2, -3, 1}, x= -2
Step 1: Initialize an empty hash table s.
Step 2: Start iterating over the array.
- For the first element 0, there is no element in the hash table that adds up to -2, so we add 0 to the hash table.
- For the second element -1, there is no element in the hash table that adds up to -2, so we add -1 to the hash table.
- For the third element 2, there is no element in the hash table that adds up to -2, so we add 2 to the hash table.
- For the fourth element -3, we find that there is a 1 in the hash table such that 1 + (-3) = -2. So, we print the pair (1, -3).
- For the fifth element 1, there is no element in the hash table that adds up to -2, so we add 1 to the hash table.
So, the output is Yes, there exist two elements in A[] whose sum is exactly x.
For the second example:
Input: arr[] = {1, -2, 1, 0, 5}, x = 0
Following the same steps, we find that there is no pair of elements in the array that add up to 0. So, the output is No, there does not exist two elements in A[] whose sum is exactly x.
Similar Questions
Given an array, check if there exist 2 elements of the array such that their sum is equal to the sum of the remaining elements of the array.
Given an array of elements. Find two elements in the array such that their sum is equal to the given element K.Input format :The first line of the input consists of the value of n.The second line of the input consists of the array of elements separated by space.The third line of the input consists of the sum.Output format :The output prints whether the array has a pair of elements with the given sum.Sample test cases :Input 1 :61 4 45 6 10 -816Output 1 :Array has two elements with given sum 16Input 2 :61 4 45 6 10 -860Output 2 :Array doesn't have two element
Sum of 2 NumbersGiven an array, check if there exist 2 elements of the array such that their sum is equal to the sum of the remaining elements of the array.Input FormatThe first line of input contains T - the number of test cases. It is followed by 2T lines, the first line contains N - the size of the array. The second line contains N integers - elements of the array.Output FormatFor each test case, print "Yes" if such elements exist, and "No" otherwise, separated by a new line.
Given an integer array and another integer element. The task is to find if the given element is present in array or not.
Have the function ArrayChallenge(arr) take the array of numbers stored in arr and return the string true if any combination of numbers in the array (excluding the largest number) can be added up to equal the largest number in the array, otherwise return the string false. For example: if arr contains [4, 6, 23, 10, 1, 3] the output should return true because 4 + 6 + 10 + 3 = 23. The array will not be empty, will not contain all the same elements, and may contain negative numbers.
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.