Problem

Submissions

Hints & solutions

Discuss

Largest Number

Easy

0/40

Average time to solve is 15m

Contributed by

7 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
5
3 2 -2 5 -3
4
1 2 3 -4

Sample Output 1 :

3
-1

Explanation For Sample Output 1 :

For test case 1 :
We can take 2 since its negative is present in the array, but the largest number is 3, whose negative is present. Hence, the answer is 3.

For test case 2 :
We cannot take any number as there does not exist any number following the given condition. Hence, the answer is -1.

Sample Input 2 :

2
6
1 2 3 5 3 -1
6
1 1 -2 2 -1 1

Sample Output 2 :

1
-2

Hint 1

Hint 2

Hint 3

For each number, try to find whether if the negative of the number exists or not.

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

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
Keep traversing until we find such element.

Time Complexity

O(N^2), where ‘N’ is the number of elements in the array.

For each number, we are traversing the whole array again that takes O(N) time. Hence, the overall time complexity is O(N^2).

Space Complexity

O(1).

We have not used any extra space. Hence, the overall space complexity is O(1).

(100% EXP penalty)

Largest Number

Console