Find a subset with greatest geometric mean
Given an array of positive integers, the task is that we find a subset of size greater than one with maximum product.
Input : arr[] = {1, 5, 7, 2, 0}; Output : 5 7 The subset containing 5 and 7 produces maximum geometric mean Input : arr[] = { 4, 3 , 5 , 9 , 8 }; Output : 8 9
A Naive Approach is to run two loops and check one-by-one array elements which give greatest geometric mean (G.M). Time complexity of this solution is O(n*n) and this solution also causes overflow.
An Efficient Solution is based on the fact that the greatest two elements would always produce the greatest mean as the question requires finding a subset of size greater than one.
Implementation:
C++
// C++ program to find a subset of size 2 or // greater with greatest geometric mean. This // program basically find largest two elements. #include <bits/stdc++.h> using namespace std; void findLargestGM( int arr[], int n) { /* There should be atleast two elements */ if (n < 2) { printf ( " Invalid Input " ); return ; } int first = INT_MIN, second = INT_MIN; for ( int i = 0; i < n ; i ++) { /* If current element is smaller than first then update both first and second */ if (arr[i] > first) { second = first; first = arr[i]; } /* If arr[i] is in between first and second then update second */ else if (arr[i] > second) second = arr[i]; } printf ( "%d %d" , second, first); } /* Driver program to test above function */ int main() { int arr[] = {12, 13, 17, 10, 34, 1}; int n = sizeof (arr)/ sizeof (arr[0]); findLargestGM(arr, n); return 0; } |
Java
// Java program to find a subset of size 2 or // greater with greatest geometric mean. This // program basically find largest two elements. class GFG { static void findLargestGM( int arr[], int n) { // There should be atleast two elements if (n < 2 ) { System.out.print( " Invalid Input " ); } int first = - 2147483648 , second = - 2147483648 ; for ( int i = 0 ; i < n ; i ++) { /* If current element is smaller than first then update both first and second */ if (arr[i] > first) { second = first; first = arr[i]; } /* If arr[i] is in between first and second then update second */ else if (arr[i] > second) second = arr[i]; } System.out.print(second + " " + first); } // Driver function public static void main(String arg[]) { int arr[] = { 12 , 13 , 17 , 10 , 34 , 1 }; int n = arr.length; findLargestGM(arr, n); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 program to find # a subset of size 2 or # greater with greatest # geometric mean. This # program basically find # largest two elements. import sys def findLargestGM(arr, n): # There should be # atleast two elements if n < 2 : print ( " Invalid Input " ) return first = - sys.maxsize - 1 second = - sys.maxsize - 1 for i in range ( 0 ,n): # If current element is # smaller than first # then update both first # and second if arr[i] > first: second = first first = arr[i] # If arr[i] is in between # first and second # then update second else if arr[i] > second: second = arr[i] print ( "%d %d" % (second, first)) # Driver program to # test above function arr = [ 12 , 13 , 17 , 10 , 34 , 1 ] n = len (arr) findLargestGM(arr, n) # This code is contributed # by Shreyanshi Arun. |
C#
// C# program to find a subset of size 2 or // greater with greatest geometric mean. This // program basically find largest two elements. using System; class GFG { static void findLargestGM( int []arr, int n) { // There should be atleast two elements if (n < 2) { Console.Write( "Invalid Input" ); } int first = -2147483648; int second = -2147483648; for ( int i = 0; i < n ; i ++) { // If current element is smaller // than first then update both // first and second if (arr[i] > first) { second = first; first = arr[i]; } // If arr[i] is in between first // and second then update second else if (arr[i] > second) second = arr[i]; } Console.Write(second + " " + first); } // Driver code public static void Main() { int []arr = {12, 13, 17, 10, 34, 1}; int n = arr.Length; findLargestGM(arr, n); } } // This code is contributed by Nitin Mittal. |
PHP
<?php // PHP program to find a subset of size 2 or // greater with greatest geometric mean. This // program basically find largest two elements. function findLargestGM( $arr , $n ) { /* There should be atleast two elements */ if ( $n < 2) { echo ( " Invalid Input " ); return ; } $first = PHP_INT_MIN; $second = PHP_INT_MIN; for ( $i = 0; $i < $n ; $i ++) { /* If current element is smaller than first then update both first and second */ if ( $arr [ $i ] > $first ) { $second = $first ; $first = $arr [ $i ]; } /* If arr[i] is in between first and second then update second */ else if ( $arr [ $i ] > $second ) $second = $arr [ $i ]; } echo ( $second . " " . $first ); } /* Driver program to test above function */ $arr = array (12, 13, 17, 10, 34, 1); $n = sizeof( $arr ); findLargestGM( $arr , $n ); // This code is contributed by Ajit. ?> |
Javascript
<script> // Javascript program to find a subset of size 2 or // greater with greatest geometric mean. This // program basically find largest two elements. function findLargestGM(arr, n) { // There should be atleast two elements if (n < 2) { document.write( "Invalid Input" ); } let first = -2147483648; let second = -2147483648; for (let i = 0; i < n ; i ++) { // If current element is smaller // than first then update both // first and second if (arr[i] > first) { second = first; first = arr[i]; } // If arr[i] is in between first // and second then update second else if (arr[i] > second) second = arr[i]; } document.write(second + " " + first); } // Driver code let arr = [ 12, 13, 17, 10, 34, 1 ]; let n = arr.length; findLargestGM(arr, n); // This code is contribute by divyesh072019 </script> |
Output
17 34
Time complexity : O(n)
Space Complexity : O(1)
Contact Us