Máximo de la suma de la longitud de los rectángulos y cuadrados formados por palos dados

Dada una array arr[] que consta de N enteros, que representan la longitud de los palos, la tarea es encontrar la suma máxima posible de todas las longitudes de los cuadrados y rectángulos construidos con estos palos. 
Nota Un solo lado se puede representar usando un solo palo.

Ejemplos:

Entrada: arr[] = {5, 3, 2, 3, 6, 3, 3} 
Salida: 12 
Suma de la longitud de los cuadrados = 3 * 4 = 12 
Suma de la longitud de los rectángulos = 0
Entrada: arr[] = {5 , 3, 2, 3, 6, 4, 4, 4, 5, 5, 5 } 
Salida: 34 
Suma de la longitud de los cuadrados = 5 * 4 = 20 
Suma de la longitud de los rectángulos = 3 * 2 + 4 * 2 = 34 
 

Enfoque: siga los pasos a continuación para resolver el problema:

• Atraviese la array para contar las frecuencias de todos los elementos de la array , digamos freq .
• Cuente las frecuencias que son al menos 2 .
• Convierta las frecuencias al valor par más pequeño más cercano.
• Convierta las frecuencias en una array unidimensional en orden descendente.
• Ahora, suma elementos hasta índices que son múltiplos de 4.
• Imprime la suma de todos estos elementos

A continuación se muestra la implementación del enfoque anterior:

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

34

Complejidad temporal: O(NlogN) 
Espacio auxiliar: O(N)