Ninja and the greatest number

Easy
0/40
Average time to solve is 10m
4 upvotes
Asked in companies
AmazonLinkedInAVIZVA

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5 
1 2 3 4 5
5
2 2 10 10 4
Sample Output 1:
5
4
Explanation of sample input 1:
In the first test case, the product of 5 and 1 is equal to 5, and 5 is also present in the ‘ARR’.    

In the second test case, the product of 2 and 2 is equal to 4, and 4 is also present in the ‘ARR’.
Sample Input 2:
2
5
2 3 4 5 9
4
10 2 20 8
Sample Output 2:
 -1
 20
Explanation for sample input 2:
In the first test case, there is no pair present in the ‘ARR’ whose product is equal to an element that is present in the ‘ARR’. 

In the second test case, the product of 10 and 2 is equal to 20, and 20 is also present in the ‘ARR’.
Hint

Can you think by finding all the pairs?

Approaches (2)
Brute Force

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: 

  1. Declare a variable ‘ANS’ in which we store our answer.
  2. 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.
  3. Finally, return ‘ANS’.
Time Complexity

O(N ^ 3), where ‘N’ is the size of ‘ARR’.


 Because for finding our answer we are using three nested loops. Hence the time complexity is O(N ^ 3).

Space Complexity

O(1)

 

Because we are not using any extra space for finding our answer.

Code Solution
(100% EXP penalty)
Ninja and the greatest number
Full screen
Console