# Three Ninja Candidate

Posted: 8 Mar, 2021

Difficulty: Easy

#### 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.
```

##### 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.
```

Approach 1

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.

Approach 2

The idea is to find the three greatest and 2 smallest numbers by traversing the array. Therefore, our approach goes like this :

- Traverse the array and compute the Greatest, second greatest, and third greatest element present in the array.
- Scan the array and compute the smallest and second smallest element present in the array.
- Return the maximum of product of greatest, second greatest, and third greatest and product of smallest, second smallest, and greatest element.

SIMILAR PROBLEMS

# Game of 3

Posted: 11 Jul, 2021

Difficulty: Easy

# Lexicographic Permutation Rank

Posted: 13 Jul, 2021

Difficulty: Moderate

# Zero Pair Sum

Posted: 22 Jul, 2021

Difficulty: Moderate

# Implement a Queue

Posted: 27 Jul, 2021

Difficulty: Easy

# Remove K Corner Elements

Posted: 31 Jul, 2021

Difficulty: Easy