Maximum of sum of length of rectangles and squares formed by given sticks
Last Updated :
08 Oct, 2023
Given an array arr[] consisting of N integers, representing the length of the sticks, the task is to find the maximum sum possible of all lengths of the squares and rectangles constructed using these sticks.
Note A single side can be represented using only a single stick.
Examples:
Input: arr[] = {5, 3, 2, 3, 6, 3, 3}
Output: 12
Sum of length of Squares= 3 * 4 = 12
Sum of length of Rectangles = 0
Input: arr[] = {5, 3, 2, 3, 6, 4, 4, 4, 5, 5, 5 }
Output: 34
Sum of length of Squares = 5 * 4 = 20
Sum of length of Rectangles = 3 * 2 + 4 * 2 = 34
Approach: Follow the steps below to solve the problem:
- Traverse the array to count the frequencies of all the array elements, say freq.
- Count frequencies which are at least 2.
- Convert frequencies to nearest smaller even value.
- Convert the frequencies to single dimensional array in descending order.
- Now, sum elements upto indices which are multiples of 4.
- Print the sum all these elements
Below is the implementation of the above approach:
C++14
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum of sum
// of lengths of rectangles and squares
// formed using given set of sticks
void findSumLength(vector<int> arr,int n)
{
// Stores the count of frequencies
// of all the array elements
map<int,int> freq;
for(int i:arr) freq[i] += 1;
// Stores frequencies which are at least 2
map<int,int> freq_2;
for (auto i:freq)
{
if (freq[i.first] >= 2)
freq_2[i.first] = freq[i.first];
}
// Convert all frequencies to nearest
// smaller even values.
vector<int> arr1;
for (auto i:freq_2)
arr1.push_back((i.first) * (freq_2[(i.first)]/2)*2);
sort(arr1.begin(), arr1.end());
// Sum of elements up to
// index of multiples of 4
int summ = 0;
for (int i:arr1)
summ += i;
// Print the sum
cout << summ;
}
// Driver Code
int main()
{
vector<int> arr = {5, 3, 2, 3, 6, 4, 4, 4, 5, 5, 5};
int n = arr.size();
findSumLength(arr, n);
return 0;
}
// This code is contributed by mohit kumar 29.
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG
{
// Function to find the maximum of sum
// of lengths of rectangles and squares
// formed using given set of sticks
static void findSumLength(int[] arr,int n)
{
// Stores the count of frequencies
// of all the array elements
HashMap<Integer,Integer>freq = new HashMap<Integer,Integer>();
for(int i:arr) {
if(freq.containsKey(i)){
freq.put(i, freq.get(i)+1);
}
else{
freq.put(i, 1);
}
}
// Stores frequencies which are at least 2
HashMap<Integer,Integer>freq_2 = new HashMap<Integer,Integer>();
for (Map.Entry<Integer,Integer> i:freq.entrySet())
{
if (i.getValue() >= 2)
freq_2.put(i.getKey() , i.getValue());
}
// Convert all frequencies to nearest
// smaller even values.
ArrayList<Integer>arr1 = new ArrayList<Integer>();
for (Map.Entry<Integer,Integer> i:freq_2.entrySet()){
arr1.add((i.getKey()) * (i.getValue()/2)*2);
}
Collections.sort(arr1);
// Sum of elements up to
// index of multiples of 4
int summ = 0;
for (int i:arr1)
summ += i;
// Print the sum
System.out.println(summ);
}
// Driver code
public static void main(String args[])
{
int[] arr = {5, 3, 2, 3, 6, 4, 4, 4, 5, 5, 5};
int n = arr.length;
findSumLength(arr, n);
}
}
// This code is contributed by shinjanpatra
# Python3 implementation of
# the above approach
from collections import Counter
# Function to find the maximum of sum
# of lengths of rectangles and squares
# formed using given set of sticks
def findSumLength(arr, n) :
# Stores the count of frequencies
# of all the array elements
freq = dict(Counter(arr))
# Stores frequencies which are at least 2
freq_2 = {}
for i in freq:
if freq[i]>= 2:
freq_2[i] = freq[i]
# Convert all frequencies to nearest
# smaller even values.
arr1 = []
for i in freq_2:
arr1.extend([i]*(freq_2[i]//2)*2)
# Sort the array in descending order
arr1.sort(reverse = True)
# Sum of elements up to
# index of multiples of 4
summ = 0
for i in range((len(arr1)//4)*4):
summ+= arr1[i]
# Print the sum
print(summ)
# Driver Code
if __name__ == "__main__" :
arr = [5, 3, 2, 3, 6, 4, 4, 4, 5, 5, 5];
n = len(arr);
findSumLength(arr, n);
using System;
using System.Collections.Generic;
class GFG{
// Function to find the maximum of sum
// of lengths of rectangles and squares
// formed using given set of sticks
static void findSumLength(List<int> arr, int n)
{
// Stores the count of frequencies
// of all the array elements
Dictionary<int,int> freq = new Dictionary<int,int>();
foreach (int i in arr){
if(freq.ContainsKey(i))
freq[i] += 1;
else
freq[i] = 1;
}
// Stores frequencies which are at least 2
Dictionary<int,int> freq_2 = new Dictionary<int,int>();
foreach(KeyValuePair<int, int> entry in freq)
{
if (freq[entry.Key] >= 2)
freq_2[entry.Key] = freq[entry.Key];
}
// Convert all frequencies to nearest
// smaller even values.
List<int> arr1 = new List<int>();
foreach(KeyValuePair<int, int> entry in freq_2)
arr1.Add(entry.Key * (freq_2[entry.Key]/2)*2);
arr1.Sort();
// Sum of elements up to
// index of multiples of 4
int summ = 0;
foreach (int i in arr1){
summ += i;
}
// Print the sum
Console.WriteLine(summ);
}
// Driver Code
public static void Main()
{
List<int> arr = new List<int>(){5, 3, 2, 3, 6, 4, 4, 4, 5, 5, 5};
int n = arr.Count;
findSumLength(arr, n);
}
}
// THIS CODE IS CONTRIBUTED BY SURENDRA_GANGWAR.
<script>
// Function to find the maximum of sum
// of lengths of rectangles and squares
// formed using given set of sticks
function findSumLength(arr, n)
{
// Stores the count of frequencies
// of all the array elements
let freq = new Map();
for(let i = 0; i < arr.length; i++)
{
if(freq.has(arr[i]))
freq.set(arr[i], freq.get(arr[i])+1);
else
freq.set(arr[i], 1);
}
// Stores frequencies which are at least 2
let freq_2 = new Map();
for(let [key, value] of freq.entries())
{
if (freq.get(key) >= 2)
freq_2.set(key,freq.get(key));
}
// Convert all frequencies to nearest
// smaller even values.
let arr1 = [];
for(let [key, value] of freq_2.entries())
arr1.push(key * Math.floor(freq_2.get(key)/2)*2);
arr1.sort(function(a, b){return a - b;});
// Sum of elements up to
// index of multiples of 4
let summ = 0;
for(let i = 0; i < arr1.length; i++){
summ += arr1[i];
}
// Print the sum
document.write(summ);
}
// Driver Code
let arr=[5, 3, 2, 3, 6, 4, 4, 4, 5, 5, 5];
let n = arr.Count;
findSumLength(arr, n);
// This code is contributed by unknown2108
</script>
Time Complexity: O(NlogN)
Auxiliary Space: O(N)
Efficient Approach:-
- In this method we will store the frequency of the elements in a unordered_map.
- After this we will just go with every element frequency and if the frequency is greater than 1 then we will take this into our answer because for a particular stick to be in a answer we will be needed atleast 2 stick of that length so that atleast we can use it in a rectangle.
- But you may think that in this way how can we say that we will get actual answer, So we will not be getting actual answer but instead of this we will be getting greater answer as per required because let's understand this with a example:-
- let's say the array is {1,2,3,1,2,3} now we will take 1+1+2+2+3+3 = 12 into our answer but the actual answer is 2+2+3+3 = 10, So it means that in out answer we have used 6 sticks and to make a rectangle or a square we need 4 stick and 6 is not divisible by 4 so we need to remove two sticks form out answer, So to make answer maximum we will remove stick of length 1 and answer will become 12-2 = 10.
- This all the thing we will be implementing in our coding part.
Implementation:-
C++
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum of sum
// of lengths of rectangles and squares
// formed using given set of sticks
void findSumLength(vector<int> arr,int n)
{
//variable to store answer
int sum=0;
unordered_map<int,int> mm;
//storing frequency of each stick
for(auto x:arr)mm[x]++;
//variable to store minimum stick length and total stick used
int mn=INT_MAX,total=0;
//iterating over map
for(auto x:mm){
//if stick is more than 1 then used only which are divisible by 2
int temp = x.second/2;
//adding length used
sum+=temp*2*(x.first);
//incrementing total sticks
total+=temp*2;
//if stick have been used then taking minimum
if(temp) mn=min(mn,x.first);
}
//if stick used not divisible by 4
if(total%4){
sum-=mn*2;
}
cout << sum;
}
// Driver Code
int main()
{
vector<int> arr = {5, 3, 2, 3, 6, 4, 4, 4, 5, 5, 5};
int n = arr.size();
findSumLength(arr, n);
return 0;
}
// This code is contributed by shubhamrajput6156.
import java.util.*;
public class Main {
// Function to find the maximum of sum
// of lengths of rectangles and squares
// formed using given set of sticks
public static void findSumLength(ArrayList<Integer> arr, int n)
{
// variable to store answer
int sum = 0;
HashMap<Integer, Integer> mm = new HashMap<Integer, Integer>();
// storing frequency of each stick
for (int i = 0; i < n; i++) {
int x = arr.get(i);
if (mm.containsKey(x)) {
mm.put(x, mm.get(x) + 1);
} else {
mm.put(x, 1);
}
}
//variable to store minimum stick length and total stick used
int mn = Integer.MAX_VALUE, total = 0;
//iterating over map
for (Map.Entry<Integer, Integer> x : mm.entrySet()) {
//if stick is more than 1 then used only which are divisible by 2
int temp = x.getValue() / 2;
//adding length used
sum += temp * 2 * (x.getKey());
//incrementing total sticks
total += temp * 2;
//if stick have been used then taking minimum
if (temp > 0) {
mn = Math.min(mn, x.getKey());
}
}
//if stick used not divisible by 4
if (total % 4 != 0) {
sum -= mn * 2;
}
System.out.print(sum);
}
// Driver Code
public static void main(String[] args) {
ArrayList<Integer> arr = new ArrayList<Integer>(Arrays.asList(5, 3, 2, 3, 6, 4, 4, 4, 5, 5, 5));
int n = arr.size();
findSumLength(arr, n);
}
}
// This code is contributed by shivhack999
def find_sum_length(arr):
# Variable to store the answer
sum_length = 0
mm = {}
# Storing the frequency of each stick
for x in arr:
if x in mm:
mm[x] += 1
else:
mm[x] = 1
# Variable to store the minimum stick length and total sticks used
mn = float('inf')
total = 0
# Iterating over the map
for x in mm:
# If stick is more than 1, use only those that are divisible by 2
temp = mm[x] // 2
# Adding length used
sum_length += temp * 2 * x
# Incrementing total sticks
total += temp * 2
# If sticks have been used, take the minimum
if temp:
mn = min(mn, x)
# If sticks used are not divisible by 4
if total % 4:
sum_length -= mn * 2
return sum_length
# Driver Code
if __name__ == "__main__":
arr = [5, 3, 2, 3, 6, 4, 4, 4, 5, 5, 5]
result = find_sum_length(arr)
print(result)
using System;
using System.Collections.Generic;
class MainClass
{
// Function to find the maximum of sum
// of lengths of rectangles and squares
// formed using a given set of sticks
public static void FindSumLength(List<int> arr, int n)
{
// variable to store answer
int sum = 0;
Dictionary<int, int> mm = new Dictionary<int, int>();
// storing frequency of each stick
for (int i = 0; i < n; i++)
{
int x = arr[i];
if (mm.ContainsKey(x))
{
mm[x]++;
}
else
{
mm[x] = 1;
}
}
// variable to store minimum stick length and total stick used
int mn = int.MaxValue, total = 0;
// iterating over the dictionary
foreach (var x in mm)
{
// if stick is more than 1 then use only those which are divisible by 2
int temp = x.Value / 2;
// adding length used
sum += temp * 2 * x.Key;
// incrementing total sticks
total += temp * 2;
// if sticks have been used then take the minimum
if (temp > 0)
{
mn = Math.Min(mn, x.Key);
}
}
// if sticks used are not divisible by 4
if (total % 4 != 0)
{
sum -= mn * 2;
}
Console.Write(sum);
}
// Driver Code
public static void Main(string[] args)
{
List<int> arr = new List<int> { 5, 3, 2, 3, 6, 4, 4, 4, 5, 5, 5 };
int n = arr.Count;
FindSumLength(arr, n);
}
}
//This code is contributed by aeroabrar_31
<script>
// Function to find the maximum sum of lengths of rectangles and squares
// formed using a given set of sticks
function findSumLength(arr) {
let sum = 0;
const mm = new Map(); // Create a map to store stick frequencies
// Count the frequency of each stick
for (let i = 0; i < arr.length; i++) {
const x = arr[i];
if (mm.has(x)) {
mm.set(x, mm.get(x) + 1);
} else {
mm.set(x, 1);
}
}
let mn = Number.MAX_VALUE; // Variable to store minimum stick length
let total = 0; // Variable to store the total number of sticks used
// Iterate over the map
mm.forEach((value, key) => {
const temp = Math.floor(value / 2); // Number of sticks that can be used
sum += temp * 2 * key; // Add to the sum of lengths
total += temp * 2; // Increment the total sticks used
if (temp > 0) {
mn = Math.min(mn, key); // Update the minimum stick length
}
});
// If the total sticks used is not divisible by 4, subtract the minimum stick length
if (total % 4 !== 0) {
sum -= mn * 2;
}
console.log(sum); // Print the maximum sum of lengths
}
const arr = [5, 3, 2, 3, 6, 4, 4, 4, 5, 5, 5];
findSumLength(arr); // Call the function with the example array
<script>
Time Complexity:- O(N), where N is the size of the array
Space Complexity:- O(N), where N is the size of the array
Similar Reads
Maximize area of triangle formed by points on sides of given rectangle
Given a rectangle [(x1, y1), (x2, y2)] denoting the coordinates of bottom-left corner and top-right corner whose sides are parallel to coordinates axes and N points on its perimeter (at least one on each side). The task is to maximize the area of a triangle formed by these points. Examples: Input: r
10 min read
Maximize sum of averages of subsequences of lengths lying in a given range
Given an array A[] consisting of N integers and two integers X and Y, the task is to find the maximum sum of the averages of each subsequences obtained by splitting the array into subsequences of lengths lying in the range [X, Y]. Note: The values of X and Y are such that it is always possible to ma
8 min read
Number of squares of maximum area in a rectangle
Given a rectangle of sides m and n. Cut the rectangle into smaller identical pieces such that each piece is a square having maximum possible side length with no leftover part of the rectangle. Print number of such squares formed.Examples: Input: 9 6 Output: 6 Rectangle can be cut into squares of siz
6 min read
Length and Breadth of rectangle such that ratio of Area to diagonal^2 is maximum
Given an array of positive integers. The task is to choose a pair of elements from the given array such that they represent the length and breadth of a rectangle and the ratio of its area and its diagonal2 is maximum. Note: The array must contains all sides of the rectangle. That is you can choose e
7 min read
Find Maximum Length Of A Square Submatrix Having Sum Of Elements At-Most K
Given a N x M matrix where N is the number of rows and M is the number of columns in the given matrix and an integer K. The task is to find the maximum length of a square submatrix having the sum of elements less than or equal to K or print 0 if no such square exits.Examples: Input: r = 4, c = 4 , k
8 min read
Maximize the length of upper boundary formed by placing given N rectangles horizontally or vertically
Given a vector of pairs, V[] denoting the width and height of N rectangles numbered from 1 to N, these rectangles are placed in contact with the horizontal axis and are adjacent from left to right in numerical order. The task is to find the maximum length of the upper boundary formed by placing each
9 min read
Number of squares of side length required to cover an N*M rectangle
Given three numbers N,M ,a . Find Number of squares of dimension a*a required to cover N*M rectangle. Note: It's allowed to cover the surface larger than the rectangle, but the rectangle has to be covered.It's not allowed to break a square.The sides of squares should be parallel to the sides of the
8 min read
Maximum Sum of two non-overlapping Subarrays of any length
Given an array A consisting of N integers, the task is to find the maximum sum of two non-overlapping subarrays of any length of the array. Note: You can select empty subarrays also. Examples: Input: N = 3, A[] = {-4, -5, -2}Output: 0Explanation: Two empty subarrays are optimal with maximum sum = 0.
6 min read
Maximum given sized rectangles that can be cut out of a sheet of paper
Given the length L and breadth B of a sheet of paper, the task is to find the maximum number of rectangles with given length l and breadth b that can be cut from this sheet of paper.Examples: Input: L = 5, B = 2, l = 14, b = 3 Output: 0 The sheet is smaller than the required rectangle. So, no rectan
6 min read
Maximum possible sum of squares of stack elements satisfying the given properties
Given two integers S and N, the task is to find the maximum possible sum of squares of N integers that can be placed in a stack such that the following properties are satisfied: The integer at the top of the stack should not be smaller than the element immediately below it.All stack elements should
7 min read