Maximize Total Area of Rectangles (SDE 2)
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.
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).
🪻༊·°Credit to niketpatel3𓂃🖊
1Example 1
2, 2, 6, and 6 can be used to form a rectangle of area 2*6=12. No other rectangles can be formed with the remaining lengths. The answer is 12 modulo (109+7)=12.2Example 2
6 and 8, and the other by reducing 4 and one of the 3s by 1 has sides of 2 and 3. The total area of these rectangles is (6*8+2*3) mod (109+7) = 54.3Example 3
5 and 3 (reduce 4 by 1), or sides of 5 and 4 (reduce 6 and one 5 by 1). The second option has a greater area, so 5*4 > 3*5.Constraints
Limits and guarantees your solution can rely on.
1 ≤ n ≤ 1052 ≤ sideLengths[i] ≤ 104 where 0 ≤ i < n