Three Ninja Candidate

Easy

0/40

Average time to solve is 10m

8 upvotes

Asked in companies

Problem statement

The Ninja squad aims to find 3 ninjas who are great collectively. Each ninja has his or her ability expressed as an integer. 3 candidates are great collectively if the product of their abilities is maximum. Given the abilities of ‘N’ ninjas in an array ARR[], find the maximum collective ability from the given pool of ninjas.

For Example :

Given N = 5,
and ARR[] = {1, 3, 5, 4, 2}
Therefore, we can see that three ninjas with ability 3,4 and 5 will give us the maximum ability and will be called great therefore the output will be 60.

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

Input format :

The first line of input contains an integer T denoting the number of test cases.

The first line of each test case contains a single integer N, where ‘N’ is the array’s size.

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 maximum product of abilities that can be had with given candidates.

The output of each test case will be printed in a separate line.

Constraints :

1 <= T <= 5
3 <=  N <= 3000
-500 <= ARR[i] <= 500 

Where ARR[i] is the array element at index I.

Time Limit: 1 sec

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Sample Input 1 :

Sample Output 1 :

60
20

Explanation of Sample Input 1 :

For the first test case: the ninjas chosen are 2nd 4th and 5th because they will give us the maximum product.Product of abilities 3 * 4 * 5 = 60. Hence the answer is 60.

For the second test case: the 3 ninjas are chosen a whose product of abilities 1*4*5 = 20. Hence the answer is 20.

Sample Input 2 :

Sample Output 2 :

64
2

Hint 1

Hint 2

Will sorting help us?

Approaches (2)

Approach 1

Approach 2

Sorting

The main idea is to sort the array in increasing order. The answer would be the maximum product of the three greatest numbers or product of the 2 smallest numbers and the greatest number.

Sort the array.
The greatest 3 numbers would be at (N-1)th, (N-2)th, and (N-3)th index.
The smallest 2 numbers would be at the 0th and 1st index.
Store the product of 3 greatest in variable takingLastThree = arr[N-1] * arr[N-2] * arr[N-3].
Store the product of 2 min numbers and greatest number in a variable takingFromBegin = arr[0] * arr[1] * arr[n-1].
The answer is the max of takingFromBegin and takingLastThree therefore, return the max of both the numbers.

Time Complexity

O(N * log(N) ), where N is the size of the given array.

As we have to sort an array of length N. Therefore, net time complexity will be O( N*log(N) ).

Space Complexity

O(1).

Since we are not using any extra space.

(100% EXP penalty)

Three Ninja Candidate

Console