Last Updated: 26 Aug, 2021
Largest Number
Easy
Asked in companies
You are given an array arr consisting of ‘N’ integers. Your task is to find the largest number, ‘K’, such that both the values ‘K’ and -‘K’ are present in the given array 'arr'. If no such number exists, then return '-1'.
For example:
Consider ‘arr’ = [1,2,-2,-1], the largest value of ‘K’ is 2, since a negative of 2 is also present in the array. Hence, the answer is 2.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows.
The first line of each test case contains an integer ‘N’, denoting the number of elements in the array.
The second line of each test case contains ‘N’ space-separated integers denoting the elements of the array.
Output Format :
For each test case, print the largest number, ‘K’, such that -’K’ is also present in the array.
The output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10
1 <= N <= 10^6
1 <= arr[i] <= 10^9
Time limit: 1 sec
Approaches
The simplest approach to solve the given problem is to iterate over the arrays and for each element, traverse the remaining array to check if its negative value exists in the array or not. After complete traversal of the array, print the maximum such number obtained.
Algorithm:
Start traversing the array from index 0
- For each index ‘i’, iterate from i+1 to the end of string and check whether
- Negative of arr[i] is present or not.
- If it is present, then update our answer as answer = max(answer,abs(arr[i]))
- Else, continue
- Negative of arr[i] is present or not.
- Keep traversing until we find such element.
The above approach can be modified using the sorting and 2-pointer approach.
We can sort the array, and then take a left pointer initialized to 0, and a right pointer initialized to the index of the last element.
Then we can do the following operations:
- Initialize our answer variable as -1 which will store the largest value.
- Sort the given array.
- Initialize two variables L=0, R=index of the last element.
- If the sum of elements at index L and index R equals 0, return the absolute value of the element at index R.
- Otherwise,
- If the sum of element at index L and index R is less than 0, then increment the value of L by 1
- Else, if the sum of element at index L and index R is greater than 0, then decrement the value of R by 1
We will use a hashmap in this approach. We will store each number in the hashmap as we iterate through the array. At each step, we check whether the negative of the current element is present in the array.
- If yes, then we will try to maximize our answer.
- Otherwise, we will continue.
Algorithm :
- Iterate through each element of the array.
- Store the frequency of each element in hashmap.
- Traverse again, and for each element, check
- If its negative value is present in hashmap or not,
- If yes, then update our answer.
- Otherwise, continue.
- If its negative value is present in hashmap or not,