Minimum sum by choosing minimum of pairs from array
Given an array A[] of n-elements. We need to select two adjacent elements and delete the larger of them and store smaller of them to another array say B[]. We need to perform this operation till array A[] contains only single element. Finally, we have to construct the array B[] in such a way that total sum of its element is minimum. Print the total sum of array B[]
Examples:
Input : A[] = {3, 4} Output : 3 Input : A[] = {2, 4, 1, 3} Output : 3
There is an easy trick to solve this question and that is always choose the smallest element of array A[] and its adjacent, delete the adjacent element and copy smallest one to array B[]. Again for next iteration we have same smallest element and any random adjacent element which is to be deleted. After n-1 operations all of elements of A[] got deleted except the smallest one and at the same time array B[] contains “n-1” elements and all are equal to smallest element of array A[].
Thus total sum of array B[] is equal to smallest * (n-1).
Implementation: Rearrange positive and negative numbers using inbuilt sort function
C++
Java
// Java program to minimize the // cost of array minimization import java.util.Arrays; public class GFG { // Returns minimum possible // sum in array B[] static int minSum( int [] A, int n) { int min_val = Arrays.stream(A).min().getAsInt(); return (min_val * (n - 1 )); } // Driver Code static public void main(String[] args) { int [] A = { 3 , 6 , 2 , 8 , 7 , 5 }; int n = A.length; System.out.println((minSum(A, n))); } } // This code is contributed by Rajput-Ji |
Python
# Python code for minimum cost of # array minimization # Function definition for minCost def minSum(A): # find the minimum element of A[] min_val = min (A); # return the answer return min_val * ( len (A) - 1 ) # driver code A = [ 7 , 2 , 3 , 4 , 5 , 6 ] print (minSum(A)) |
C#
// C# program to minimize the // cost of array minimization using System; using System.Linq; public class GFG { // Returns minimum possible // sum in array B[] static int minSum( int []A, int n) { int min_val = A.Min(); return (min_val * (n - 1)); } // Driver Code static public void Main() { int []A = {3, 6, 2, 8, 7, 5}; int n = A.Length; Console.WriteLine(minSum(A, n)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to minimize the // cost of array minimization // Returns minimum possible // sum in array B[] function minSum( $A , $n ) { $min_val = min( $A ); return ( $min_val * ( $n - 1)); } // Driver Code $A = array (3, 6, 2, 8, 7, 5); $n = count ( $A ); echo minSum( $A , $n ); // This code is contributed by vt_m. ?> |
Javascript
<script> // JavaScript program to minimize the cost // of array minimization // Returns minimum possible sum in // array B[] function minSum(A, n) { let min_val = Math.min(...A); return (min_val * (n-1)); } // driver function let A = [3, 6, 2, 8, 7, 5]; let n = A.length; document.write(minSum(A, n)); // This code is contributed by Mayank Tyagi </script> |
10
Time Complexity : O(n) in finding the smallest element of the array.
Auxiliary Space: O(1)
Contact Us