Maximum of sum of length of rectangles and squares formed by given sticks
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. |
Java
/*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
# 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); |
C#
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. |
Javascript
<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> |
34
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. |
Java
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 |
Python3
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) |
C#
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 |
Javascript
<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> |
34
Time Complexity:- O(N), where N is the size of the array
Space Complexity:- O(N), where N is the size of the array