Dada una array de N elementos positivos, encuentre el número de cuádruples, (i, j, k, m) tales que i < j < k < m tales que el producto a i a j a k a m sea el máximo posible .
Ejemplos:
Input : N = 7, arr = {1, 2, 3, 3, 3, 3, 5}
Output : 4
Explanation
The maximum quadruple product possible is 135, which can be
achieved by the following quadruples {i, j, k, m} such that aiajakam = 135:
1) a3a4a5a7
2) a3a4a6a7
3) a4a5a6a7
4) a3a5a6a7
Input : N = 4, arr = {1, 5, 2, 1}
Output : 1
Explanation
The maximum quadruple product possible is 10, which can be
achieved by the following quadruple {1, 2, 3, 4} as a1a2a3a4 = 10
Fuerza bruta: O(n 4 )
Genera todos los cuádruples posibles y cuenta los cuádruples, dando el producto máximo.
Solución optimizada :
es fácil ver que el producto de los cuatro números más grandes sería el máximo. Entonces, el problema ahora se puede reducir a encontrar el número de formas de seleccionar los cuatro elementos más grandes. Para hacerlo, mantenemos una array de frecuencias que almacena la frecuencia de cada elemento de la array.
Supongamos que el elemento más grande es X con frecuencia F X , entonces si la frecuencia de este elemento es >= 4, lo mejor es seleccionar los cuatro elementos como X, X, X, dado un producto máximo y el número de formas de hacerlo es F X C 4
y si la frecuencia es menor que 4, el número de formas de seleccionar esto es 1 y ahora el número requerido de elementos es 4 – F X. Para el segundo elemento, digamos Y, el número de formas es: F X C restantes_opciones . Las opciones restantes indican la cantidad de elementos adicionales que debemos seleccionar después de seleccionar el primer elemento. Si en algún momento, las opciones restantes = 0, significa que se seleccionaron los cuádruples, por lo que podemos detener el algoritmo.
C++
// CPP program to find the number of Quadruples
// having maximum product
#include <bits/stdc++.h>
using namespace std;
// Returns the number of ways to select r objects
// out of available n choices
int NCR(int n, int r)
{
int numerator = 1;
int denominator = 1;
// ncr = (n * (n - 1) * (n - 2) * .....
// ... (n - r + 1)) / (r * (r - 1) * ... * 1)
while (r > 0) {
numerator *= n;
denominator *= r;
n--;
r--;
}
return (numerator / denominator);
}
// Returns the number of quadruples having maximum product
int findWays(int arr[], int n)
{
// stores the frequency of each element
map<int, int> count;
if (n < 4)
return 0;
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}
// remaining_choices denotes the remaining
// elements to select inorder to form quadruple
int remaining_choices = 4;
int ans = 1;
// traverse the elements of the map in reverse order
for (auto iter = count.rbegin(); iter != count.rend(); ++iter) {
int number = iter->first;
int frequency = iter->second;
// If Frequency of element < remaining choices,
// select all of these elements, else select only
// the number of elements required
int toSelect = min(remaining_choices, frequency);
ans = ans * NCR(frequency, toSelect);
// Decrement remaining_choices acc to the number
// of the current elements selected
remaining_choices -= toSelect;
// if the quadruple is formed stop the algorithm
if (!remaining_choices) {
break;
}
}
return ans;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 3, 3, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int maxQuadrupleWays = findWays(arr, n);
cout << maxQuadrupleWays;
return 0;
}
Java
// Java program to find the number of Quadruples
// having maximum product
import java.util.*;
class Solution
{
// Returns the number of ways to select r objects
// out of available n choices
static int NCR(int n, int r)
{
int numerator = 1;
int denominator = 1;
// ncr = (n * (n - 1) * (n - 2) * .....
// ... (n - r + 1)) / (r * (r - 1) * ... * 1)
while (r > 0) {
numerator *= n;
denominator *= r;
n--;
r--;
}
return (numerator / denominator);
}
// Returns the number of quadruples having maximum product
static int findWays(int arr[], int n)
{
// stores the frequency of each element
HashMap<Integer,Integer> count= new HashMap<Integer,Integer>();
if (n < 4)
return 0;
for (int i = 0; i < n; i++) {
count.put(arr[i],(count.get(arr[i])==null?0🙁int)count.get(arr[i])));
}
// remaining_choices denotes the remaining
// elements to select inorder to form quadruple
int remaining_choices = 4;
int ans = 1;
// Getting an iterator
Iterator hmIterator = count.entrySet().iterator();
while (hmIterator.hasNext()) {
Map.Entry mapElement = (Map.Entry)hmIterator.next();
int number =(int) mapElement.getKey();
int frequency =(int)mapElement.getValue();
// If Frequency of element < remaining choices,
// select all of these elements, else select only
// the number of elements required
int toSelect = Math.min(remaining_choices, frequency);
ans = ans * NCR(frequency, toSelect);
// Decrement remaining_choices acc to the number
// of the current elements selected
remaining_choices -= toSelect;
// if the quadruple is formed stop the algorithm
if (remaining_choices==0) {
break;
}
}
return ans;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 1, 2, 3, 3, 3, 5 };
int n = arr.length;
int maxQuadrupleWays = findWays(arr, n);
System.out.print( maxQuadrupleWays);
}
}
//contributed by Arnab Kundu
Python3
# Python3 program to find # the number of Quadruples # having maximum product from collections import defaultdict # Returns the number of ways # to select r objects out of # available n choices def NCR(n, r): numerator = 1 denominator = 1 # ncr = (n * (n - 1) * # (n - 2) * ..... # ... (n - r + 1)) / # (r * (r - 1) * ... * 1) while (r > 0): numerator *= n denominator *= r n -= 1 r -= 1 return (numerator // denominator) # Returns the number of # quadruples having # maximum product def findWays(arr, n): # stores the frequency # of each element count = defaultdict (int) if (n < 4): return 0 for i in range (n): count[arr[i]] += 1 # remaining_choices denotes # the remaining elements to # select inorder to form quadruple remaining_choices = 4 ans = 1 # traverse the elements of # the map in reverse order for it in reversed(sorted(count.keys())): number = it frequency = count[it] # If Frequency of element < # remaining choices, select # all of these elements, # else select only the # number of elements required toSelect = min(remaining_choices, frequency) ans = ans * NCR(frequency, toSelect) # Decrement remaining_choices # acc to the number of the # current elements selected remaining_choices -= toSelect # if the quadruple is # formed stop the algorithm if (not remaining_choices): break return ans # Driver Code if __name__ == "__main__": arr = [1, 2, 3, 3, 3, 5] n = len(arr) maxQuadrupleWays = findWays(arr, n) print (maxQuadrupleWays) # This code is contributed by Chitranayal
Javascript
<script>
// Javascript program to find the number of Quadruples
// having maximum product
// Returns the number of ways to select r objects
// out of available n choices
function NCR(n,r)
{
let numerator = 1;
let denominator = 1;
// ncr = (n * (n - 1) * (n - 2) * .....
// ... (n - r + 1)) / (r * (r - 1) * ... * 1)
while (r > 0) {
numerator *= n;
denominator *= r;
n--;
r--;
}
return Math.floor(numerator / denominator);
}
// Returns the number of quadruples having maximum product
function findWays(arr,n)
{
// stores the frequency of each element
let count= new Map();
if (n < 4)
return 0;
for (let i = 0; i < n; i++) {
count.set(arr[i],(count.get(arr[i])==
null?0:count.get(arr[i])+1));
}
// remaining_choices denotes the remaining
// elements to select inorder to form quadruple
let remaining_choices = 4;
let ans = 1;
// Getting an iterator
for(let [key, value] of count.entries()) {
let number =key;
let frequency =value;
// If Frequency of element < remaining choices,
// select all of these elements, else select only
// the number of elements required
let toSelect = Math.min(remaining_choices, frequency);
ans = ans * NCR(frequency, toSelect);
// Decrement remaining_choices acc to the number
// of the current elements selected
remaining_choices -= toSelect;
// if the quadruple is formed stop the algorithm
if (remaining_choices==0) {
break;
}
}
return ans;
}
// Driver Code
let arr=[1, 2, 3, 3, 3, 5 ];
let n = arr.length;
let maxQuadrupleWays = findWays(arr, n);
document.write( maxQuadrupleWays);
// This code is contributed by rag2127
</script>
Producción:
1
Complejidad de tiempo: O(NlogN), donde N es el tamaño de la array.
Espacio Auxiliar: O(N)