Last Updated: 22 Apr, 2021
Sum of Two Values
Moderate
Asked in companies
You are given an array of positive integers, ‘NUMS’, and provided with an integer ‘K’. Your take is to find out whether it is possible to find two distinct elements of ‘NUMS’ whose sum is equal to ‘K’.
By distinct we mean the index of the elements should be distinct, not necessarily their value.
Input Format:
The first line contains an integer ‘T’, which denotes the number of test cases to be run.
Then, the ‘T’ test cases follow.
The first line of each test case contains two positive integers, ‘N’ (denoting the size of the array ‘NUMS’) and ‘K’.
The second line of each test case contains ‘N’ space-separated positive integers denoting the array elements.
Output Format:
For each test case, print the indexes(1 indexed) of the two elements which sum up to ‘K’. If an answer does not exist, print -1 -1 instead. If multiple answers exist, print any of them.
The output will be checked by the system, for a correct answer "YES" will be printed otherwise "NO" will be printed.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^6
1 <= ‘K’ <= 10^6
1 <= ‘NUMS[i]’ <= 10^6
Time Limit: 1 sec
Approaches
- Look into every pair of numbers of NUMS(using 2 nested loops) and check if any of them satisfy the required conditions.
- If any pair of numbers sum up to K, return their indices, otherwise, continue for the remaining pairs.
- If no pair satisfies the condition, return -1 -1 at the end.
- Create a new array STORE which, instead of storing only the array element, will store both the array element’s value and its original index in NUMS as a pair.
- Sort this new array STORE.
- Keep two pointers, LEFT which is currently initialized to 0, and RIGHT which is currently initialized to N-1.
- Keep repeating the below steps until LEFT’s index is less than RIGHT’s index
- If STORE[LEFT]’s value + STORE[RIGHT]’s value = K, we have got a valid answer. Print STORE[LEFT]’s index, STORE[RIGHT]’s index and break out of the program.
- If STORE[LEFT]’s value + STORE[RIGHT]’s value < K, we need to get a higher value, therefore increment LEFT’s position by 1.
- If STORE[LEFT]’s value + STORE[RIGHT]’s value > K, we need a lower value, therefore decrease RIGHT’s position by 1.
- Continue this process.
- In the end, if no pair is found, return -1 -1.
- We can use this observation that, if we are currently looking into a number NUM in NUMS, then for the answer to exist K - NUM should also exist in NUMS.
- Traverse the array NUMS.
- Keep an unordered hashmap, STORE which will store the index of the elements which have been traversed.
- Suppose we are looking at NUM which is at index i. Search if its complement K - NUM exists in STORE, and if does, return the current index i and STORE[K - NUM].
- Otherwise, continue traversing the array.
- In the end, if no pair is found, return -1 -1.
Similar problems