Last Updated: 8 Apr, 2021

Ninja and the greatest number

Easy

Asked in companies

Solve now

Problem statement

Ninja has been given an array/list of integers ‘ARR’ of size ‘N’. Ninja has to find the greatest number present in the ‘ARR’ such that this number is also equal to the product of the two elements present in the ‘ARR’.

Note:

1. The pair should be from different indices. 
2. If no such number is present in the ‘ARR’, then return -1.

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a single space-separated integer ‘N’ which represents the size of ‘ARR’.

The next line contains ‘N’ single space-separated integers representing the values of the ‘ARR’.

Output Format:

For each test case, print and integer denoting the greatest number present in the ‘ARR,’ such that the product of two elements present in the ‘ARR’ is equal to this element. Otherwise, print -1.

Output for every test case will be printed in a separate line.

Note:

You don’t need to print anything; It has already been taken care of. Just implement the given function.

Constraints:

1 <= ‘T’ <= 50
2 <= ‘N’ <= 10^4
1 <= ‘ARR[i]’ <= 10^5

Time limit: 1 sec

Solve now

Approaches

01 Approach

The basic idea is to find all the pairs and check if the product of two elements of a pair is equal to an element that is present in the ‘ARR’.

The steps are as follows:

Declare a variable ‘ANS’ in which we store our answer.
Run a loop for ‘i’ = 0 to ‘N’:
- Run a loop for ‘j’ = 0 to ‘N’ - 1.
  - Run a loop for ‘k’ = ‘j’ + 1 to ‘N’:
  - If ‘ARR[j]’ * ‘ARR[k]’ is equal to ‘ARR[i]’:
    - ‘ANS’ = MAX(‘ANS’, ‘ARR’[i]).
    - Break.
Finally, return ‘ANS’.

Solve now

02 Approach

The basic idea of this approach is to store all values of the ‘ARR’ in a HashMap ‘ALL_VALUES’. Then sort the ‘ARR’.

Let's assume ‘ans’ = ‘a’ * ‘b’.

If ‘a’ and ‘b’ are equal then ‘ans’ = ‘a’ * ‘a’ or ‘ans’ = ‘a’ ^ 2.

So we can also check the second element of the pair till sqrt of ‘ans’.

The steps are as follows:

Declare a HashMap ‘ALL_VALUES’ as discussed above and store values of the ‘ARR’ in HashMap.
Sort the ‘ARR’.
Run a loop for ‘j’ = ‘N’ - 1 to 1:
- Run a loop for ‘j’ = 0 to less than ‘i’ and ‘ARR’[j] less than equal to sqrt(‘ARR[i]’):
  - If ‘ARR’[i] % ‘ARR[j]’ is equal to 0:
    - Store ‘ARR[i]’ / ‘ARR[j]’ in a variable ‘RESULT’.
    - If ‘RESULT’ is not equal to ‘ARR[j]’ and this value is present in HashMap:
      1. Return ‘ARR[i]’.
    - Else if ‘RESULT’ is equal to ‘ARR[j]’ and this value is present in HashMap and greater than 1:
      1. Return ‘ARR[i]’.
Return -1.

Solve now