Given an array of positive integers. We are required to write a program to print the minimum product of any two numbers of the given array.
Examples:
Input : 11 8 5 7 5 100 Output : 25 Explanation : The minimum product of any two numbers will be 5 * 5 = 25. Input : 198 76 544 123 154 675 Output : 9348 Explanation : The minimum product of any two numbers will be 76 * 123 = 9348.
Simple Approach: A simple approach will be to run two nested loops to generate all possible pair of elements and keep track of the minimum product.
Java
// Java program to find minimum product of any two numbers in an arrayimport java.util.Arrays;public class MinProductOfTwo { // Driver Code public static void main(String[] args) { int[] arr = { 11, 8, 5, 7, 5, 100 }; int n = arr.length; // Function Call int minProduct = printMinimumProduct(arr); System.out.println(minProduct); } public static int printMinimumProduct(int[] arr) { int minProduct = Integer.MAX_VALUE; // loop through all possible pairs of array elements and find minimum product for (int i = 0; i < arr.length - 1; i++) { for (int j = i + 1; j < arr.length; j++) { int product = arr[i] * arr[j]; // if minProduct is greater than the current product of 2 elements // then update the minProduct with that one if (product < minProduct) { minProduct = product; } } } // return minimum product return minProduct; }} |
25
Time Complexity: O( n * n)
Auxiliary Space: O( 1 )
Better Approach: An efficient approach will be to first sort the given array and print the product of first two numbers, sorting will take O(n log n). Answer will be then a[0] * a[1]
Java
// Java program to find the minimum product of any two// numbers in an arrayimport java.util.Arrays;public class GFG { // Function to find the minimum product of any two // numbers in an array static long findMinimumProduct(int[] arr) { int n = arr.length; // sort the array Arrays.sort(arr); // return the product of first two // numbers return (long)arr[0] * arr[1]; } // Driver code public static void main(String[] args) { // Input array int[] arr = { 11, 8 , 5 , 7 , 5 , 100 }; // Function Call long minProduct = findMinimumProduct(arr); // Printing final answer System.out.println(minProduct); }} |
25
Time Complexity: O( n * log(n))
Auxiliary Space: O( 1 )
Best Approach: The idea is linearly traverse given array and keep track of minimum two elements. Finally return product of two minimum elements.
Below is the implementation of above approach.
Java
// Java program to calculate minimum// product of a pairimport java.util.*;class GFG { // Function to calculate minimum product // of pair static int printMinimumProduct(int arr[], int n) { // Initialize first and second // minimums. It is assumed that the // array has at least two elements. int first_min = Math.min(arr[0], arr[1]); int second_min = Math.max(arr[0], arr[1]); // Traverse remaining array and keep // track of two minimum elements (Note // that the two minimum elements may // be same if minimum element appears // more than once) // more than once) for (int i = 2; i < n; i++) { if (arr[i] < first_min) { second_min = first_min; first_min = arr[i]; } else if (arr[i] < second_min) second_min = arr[i]; } return first_min * second_min; } /* Driver program to test above function */ public static void main(String[] args) { int a[] = { 11, 8 , 5 , 7 , 5 , 100 }; int n = a.length; System.out.print(printMinimumProduct(a,n)); }}// This code is contributed by Arnav Kr. Mandal. |
25
Time Complexity: O(n)
Auxiliary Space: O(1) Please refer complete article on Minimum product pair an array of positive Integers for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
