Given an array arr[] of N integers and a positive integer K, the task is to minimize the sum of the array elements after performing the given operation atmost one time. The operation is to choose a subarray and divide all elements of the subarray by K. Find and print the minimum possible sum.
Examples:
Input: arr[] = {1, -2, 3}, K = 2
Output: 0.5
Choose the subarray {3} and divide them by K
The array becomes {1, -2, 1.5} where 1 – 2 + 1.5 = 0.5
Input: arr[] = {-1, -2, -3, -5}, K = 4
Output: -11
There is no need to perform the operation as the
sum of the array elements is already minimum.
Approach:
- Find the maximum sum subarray using Kadane’s Algorithm say maxSum as it will be the subarray which will be contributing in maximizing the sum of the array.
- Now there are two cases:
- maxSum > 0: Divide every element of the found subarray with K and the sum of the resultant array will be minimum possible.
- maxSum ? 0: No need to perform the operation as the sum of the array is already minimum.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the maximum subarray sum int maxSubArraySum( int a[], int size) { int max_so_far = INT_MIN, max_ending_here = 0; for ( int i = 0; i < size; i++) { max_ending_here = max_ending_here + a[i]; if (max_so_far < max_ending_here) max_so_far = max_ending_here; if (max_ending_here < 0) max_ending_here = 0; } return max_so_far; } // Function to return the minimized sum // of the array elements after performing // the given operation double minimizedSum( int a[], int n, int K) { // Find maximum subarray sum int sum = maxSubArraySum(a, n); double totalSum = 0; // Find total sum of the array for ( int i = 0; i < n; i++) totalSum += a[i]; // Maximum subarray sum is already negative if (sum < 0) return totalSum; // Choose the subarray whose sum is // maximum and divide all elements by K totalSum = totalSum - sum + ( double )sum / ( double )K; return totalSum; } // Driver code int main() { int a[] = { 1, -2, 3 }; int n = sizeof (a) / sizeof (a[0]); int K = 2; cout << minimizedSum(a, n, K); return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { // Function to return the maximum subarray sum static int maxSubArraySum( int a[], int size) { int max_so_far = Integer.MIN_VALUE, max_ending_here = 0 ; for ( int i = 0 ; i < size; i++) { max_ending_here = max_ending_here + a[i]; if (max_so_far < max_ending_here) max_so_far = max_ending_here; if (max_ending_here < 0 ) max_ending_here = 0 ; } return max_so_far; } // Function to return the minimized sum // of the array elements after performing // the given operation static double minimizedSum( int a[], int n, int K) { // Find maximum subarray sum int sum = maxSubArraySum(a, n); double totalSum = 0 ; // Find total sum of the array for ( int i = 0 ; i < n; i++) totalSum += a[i]; // Maximum subarray sum is already negative if (sum < 0 ) return totalSum; // Choose the subarray whose sum is // maximum and divide all elements by K totalSum = totalSum - sum + ( double )sum / ( double )K; return totalSum; } // Driver code public static void main(String []args) { int a[] = { 1 , - 2 , 3 }; int n = a.length; int K = 2 ; System.out.println(minimizedSum(a, n, K)); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach import sys # Function to return the maximum subarray sum def maxSubArraySum(a, size) : max_so_far = - (sys.maxsize - 1 ); max_ending_here = 0 ; for i in range (size) : max_ending_here = max_ending_here + a[i]; if (max_so_far < max_ending_here) : max_so_far = max_ending_here; if (max_ending_here < 0 ) : max_ending_here = 0 ; return max_so_far; # Function to return the minimized sum # of the array elements after performing # the given operation def minimizedSum(a, n, K) : # Find maximum subarray sum sum = maxSubArraySum(a, n); totalSum = 0 ; # Find total sum of the array for i in range (n) : totalSum + = a[i]; # Maximum subarray sum is already negative if ( sum < 0 ) : return totalSum; # Choose the subarray whose sum is # maximum and divide all elements by K totalSum = totalSum - sum + sum / K; return totalSum; # Driver code if __name__ = = "__main__" : a = [ 1 , - 2 , 3 ]; n = len (a); K = 2 ; print (minimizedSum(a, n, K)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System; class GFG { // Function to return the maximum subarray sum static int maxSubArraySum( int []a, int size) { int max_so_far = int .MinValue, max_ending_here = 0; for ( int i = 0; i < size; i++) { max_ending_here = max_ending_here + a[i]; if (max_so_far < max_ending_here) max_so_far = max_ending_here; if (max_ending_here < 0) max_ending_here = 0; } return max_so_far; } // Function to return the minimized sum // of the array elements after performing // the given operation static double minimizedSum( int []a, int n, int K) { // Find maximum subarray sum int sum = maxSubArraySum(a, n); double totalSum = 0; // Find total sum of the array for ( int i = 0; i < n; i++) totalSum += a[i]; // Maximum subarray sum is already negative if (sum < 0) return totalSum; // Choose the subarray whose sum is // maximum and divide all elements by K totalSum = totalSum - sum + ( double )sum / ( double )K; return totalSum; } // Driver code public static void Main(String []args) { int []a = { 1, -2, 3 }; int n = a.Length; int K = 2; Console.WriteLine(minimizedSum(a, n, K)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript implementation of the approach // Function to return the maximum subarray sum function maxSubArraySum(a, size) { var max_so_far = -1000000000, max_ending_here = 0; for ( var i = 0; i < size; i++) { max_ending_here = max_ending_here + a[i]; if (max_so_far < max_ending_here) max_so_far = max_ending_here; if (max_ending_here < 0) max_ending_here = 0; } return max_so_far; } // Function to return the minimized sum // of the array elements after performing // the given operation function minimizedSum(a, n, K) { // Find maximum subarray sum var sum = maxSubArraySum(a, n); var totalSum = 0; // Find total sum of the array for ( var i = 0; i < n; i++) totalSum += a[i]; // Maximum subarray sum is already negative if (sum < 0) return totalSum; // Choose the subarray whose sum is // maximum and divide all elements by K totalSum = totalSum - sum + sum / K; return totalSum; } // Driver code var a = [1, -2, 3]; var n = a.length; var K = 2; document.write( minimizedSum(a, n, K)); // This code is contributed by rrrtnx. </script> |
0.5
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!