Given an array of N positive elements, find the number of quadruples, (i, j, k, m) such that i < j < k < m such that the product aiajakam is the maximum possible.
Examples:
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
Brute Force: O(n4)
Generate all possible quadruple and count the quadruples, giving the maximum product.
Optimized Solution: It is easy to see that the product of the four largest numbers would be the maximum. So, the problem can now be reduced to finding the number of ways of selecting the four largest elements. To do so, we maintain a frequency array that stores the frequency of each element of the array.
Suppose the largest element is X with frequency FX, then if the frequency of this element is >= 4, it is best suited to select the four elements as X, X, X, as that, given a maximum product and the number of ways to do so is FX C 4
and if the frequency is less than 4, the number of ways to select this is 1 and now the required number of elements is 4 – FX. For the second element, say Y, the number of ways are: FX C remaining_choices. Remaining choices denotes the number of additional elements we need to select after selecting the first element. If at any time, the remaining_choices = 0, it means the quadruples are selected, so we can stop the algorithm.
Implementation:
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 choicesint 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 productint 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 Codeint 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 productimport java.util.*;class Solution{// Returns the number of ways to select r objects// out of available n choicesstatic 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 productstatic 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 Codepublic 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 productfrom collections import defaultdict# Returns the number of ways # to select r objects out of# available n choicesdef 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 productdef 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 Codeif __name__ == "__main__": arr = [1, 2, 3, 3, 3, 5] n = len(arr) maxQuadrupleWays = findWays(arr, n) print (maxQuadrupleWays)# This code is contributed by Chitranayal |
C#
// C# program to find the number of Quadruples// having maximum productusing System;using System.Collections.Generic;class GFG { // 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 Dictionary<int, int> count = new Dictionary<int, int>(); if (n < 4) return 0; for (int i = 0; i < n; i++) { if (!count.ContainsKey(arr[i])) count[arr[i]] = 1; else count[arr[i]] += 1; } // remaining_choices denotes the remaining // elements to select inorder to form quadruple int remaining_choices = 4; int ans = 1; List<int> mapElements = new List<int>(count.Keys); mapElements.Sort(); mapElements.Reverse(); // Getting an iterator foreach(var number in mapElements) { int frequency = count[number]; // 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); Console.WriteLine(maxQuadrupleWays); }}// This code is contributed by phasing17 |
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 choicesfunction 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 productfunction 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 Codelet 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> |
Output
1
Complexity Analysis:
- Time Complexity: O(NlogN), where N is the size of the array.
- Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
