Amazon games have introduced a new mathematical game for kids. You will be given n
sticks and the player is required to form rectangles from those sticks.
Formally, given an array of n
integers representing the lengths of the sticks, you are required to create rectangles using those sticks. Note that a particular stick can be used in at most one rectangle and in order to create a rectangle we must have exactly two pairs of sticks with the same lengths. For example, you can create a rectangle using sticks of lengths [2, 2, 5, 5]
and [4, 4, 4, 4]
but not with [3, 3, 5, 8]
. The goal of the game is to maximize the total sum of areas of all the rectangles formed.
In order to make the game more interesting, we are allowed to reduce any integer by at most 1. Given the array sideLengths
, representing the length of the sticks, find the maximum sum of areas of rectangles that can be formed such that each element of the array can be used as length or breadth of at most one rectangle and you are allowed to decrease any integer by at most 1. Since this number can be quite large, return the answer modulo 10^9+7
.
Note: It is not a requirement that all side lengths be used. Also, a modulo b
here represents the remainder obtained when an integer a
is divided by an integer b
.
Function Description
Complete the function getMaxTotalArea
in the editor.
getMaxTotalArea
has the following parameter(s):
int sideLengths[n]
: the side lengths that can be used to form rectangles
Returns
int
: the maximum total area of the rectangles that can be formed, modulo (109+7)
.
Example 1:
Input: sideLengths = [2, 6, 2, 6, 3, 5]
Output: 12
Explanation:The lengths2, 2, 6,
and6
can be used to form a rectangle of area2*6=12
. No other rectangles can be formed with the remaining lengths. The answer is12
modulo(109+7)=12
.
Example 2:
Input: sideLengths = [2, 3, 3, 4, 6, 8, 8, 6]
Output: 54
Explanation:Two rectangles can be formed. One has sides of6
and8
, and the other by reducing4
and one of the3s
by1
has sides of2
and3
. The total area of these rectangles is(6*8+2*3)
mod(109+7) = 54
.
Example 3:
Input: sideLengths = [3, 4, 5, 5, 6]
Output: 20
Explanation:The rectangle can have either sides of5
and3
(reduce4
by1
), or sides of5
and4
(reduce6
and one5
by1
). The second option has a greater area, so5*4 > 3*5
.
1 ≤ n ≤ 105
2 ≤ sideLengths[i] ≤ 104
where0 ≤ i < n
input:
output: