Minimize Array sum by replacing L and R elements from both end with X and Y
Given an array A[] of N integers and 2 integers X and Y. The task is to minimize the sum of all elements of the array by choosing L and R and replacing the initial L elements with X and the R elements from the end with Y.
Examples:
Input: N = 5, X = 4, Y = 3, A[] = {5, 5, 0, 6, 3}
Output: 14
Explanation: We choose L = 2 and R = 2. On replacing the initial 2 elements of an array with X(=4) and ending 2 elements with Y(=3), we get A = {4, 4, 0, 3, 3} whose sum is 14.Input: N = 4, X = 10, Y = 10, A[] = {1, 2, 3, 4}
Output: 10
Explanation: We choose both L = 0 and R = 0. So no replacements are done on the array and the sum of elements of the original array is returned.
Approach: This can be solved with the following idea:
By using prefix and suffix array sum, check the minimum upon choosing all X, Y, or original array sum.
The following approach can be used to solve the problem :
- Declare 2 arrays, say Pre[] and Suff[], each of size N+1.
- Pre[i] stores the value of the minimum possible sum of initial i elements of the array (i.e. either replace all the initial i elements by X or add the value of the current element to the Pre[i-1]).
- Similarly, Suff[i] stores the value of the minimum possible sum of the i elements of the array from the end.
- The final answer would be the minimum of all (Pre[i]+Suff[i]) for i ranging from 0 to N.
Below is the implementation of the above approch.
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Function to Minimize sum of array by replacing // initial L elements with X and R elements from // end with Y int minimumSum( int N, int A[], int X, int Y) { // Declaring 2 arrays Pre[] and Suff[] to // store the minimum possible sum of each // subarray from beginning and end respectively int Pre[N + 1]; int Suff[N + 1]; Pre[0] = 0, Suff[0] = 0; // Initializing answer as a large value int answer = INT_MAX; // Iterating through 1 to N and Calculating // the values of Pre and Suff for each index for ( int i = 1; i <= N; i++) { Pre[i] = min(X * i, Pre[i - 1] + A[i - 1]); Suff[i] = min(Y * i, Suff[i - 1] + A[N - i]); } // Calculating answer as the minimum of // all possible Pre[i]+Suff[N-i] for ( int i = 0; i <= N; i++) { answer = min(answer, Pre[i] + Suff[N - i]); } // Returning final answer return answer; } // Driver code int main() { int N = 5, X = 4, Y = 3; int A[] = { 5, 5, 0, 6, 3 }; // Function call int ans = minimumSum(N, A, X, Y); cout << ans; return 0; } |
Java
// Java code for the above approach import java.util.*; class GFG { // Function to Minimize sum of array by replacing // initial L elements with X and R elements from // end with Y public static int minimumSum( int N, int A[], int X, int Y) { // Declaring 2 arrays Pre[] and Suff[] to // store the minimum possible sum of each // subarray from beginning and end respectively int [] Pre = new int [N + 1 ]; int [] Suff = new int [N + 1 ]; Pre[ 0 ] = 0 ; Suff[ 0 ] = 0 ; // Initializing answer as a large value int answer = Integer.MAX_VALUE; // Iterating through 1 to N and Calculating // the values of Pre and Suff for each index for ( int i = 1 ; i <= N; i++) { Pre[i] = Math.min(X * i, Pre[i - 1 ] + A[i - 1 ]); Suff[i] = Math.min(Y * i, Suff[i - 1 ] + A[N - i]); } // Calculating answer as the minimum of // all possible Pre[i]+Suff[N-i] for ( int i = 0 ; i <= N; i++) { answer = Math.min(answer, Pre[i] + Suff[N - i]); } // Returning final answer return answer; } // Driver code public static void main(String[] args) { int N = 5 , X = 4 , Y = 3 ; int [] A = { 5 , 5 , 0 , 6 , 3 }; // Function call int ans = minimumSum(N, A, X, Y); System.out.println(ans); } } |
Python3
# Function to Minimize sum of array by replacing # initial L elements with X and R elements from # end with Y def minimumSum(N, A, X, Y): # Declaring 2 arrays Pre[] and Suff[] to # store the minimum possible sum of each # subarray from beginning and end respectively Pre = [ 0 ] * (N + 1 ) Suff = [ 0 ] * (N + 1 ) Pre[ 0 ], Suff[ 0 ] = 0 , 0 # Initializing answer as a large value answer = float ( 'inf' ) # Iterating through 1 to N and Calculating # the values of Pre and Suff for each index for i in range ( 1 , N + 1 ): Pre[i] = min (X * i, Pre[i - 1 ] + A[i - 1 ]) Suff[i] = min (Y * i, Suff[i - 1 ] + A[N - i]) # Calculating answer as the minimum of # all possible Pre[i]+Suff[N-i] for i in range (N + 1 ): answer = min (answer, Pre[i] + Suff[N - i]) # Returning final answer return answer # Driver code N = 5 X = 4 Y = 3 A = [ 5 , 5 , 0 , 6 , 3 ] # Function call ans = minimumSum(N, A, X, Y) print (ans) |
C#
// c# code for the above approach using System; class GFG { // Function to Minimize sum of array by replacing // initial L elements with X and R elements from // end with Y public static int MinimumSum( int N, int [] A, int X, int Y) { // Declaring 2 arrays Pre[] and Suff[] to // store the minimum possible sum of each // subarray from beginning and end respectively int [] Pre = new int [N + 1]; int [] Suff = new int [N + 1]; Pre[0] = 0; Suff[0] = 0; // Initializing answer as a large value int answer = int .MaxValue; // Iterating through 1 to N and Calculating // the values of Pre and Suff for each index for ( int i = 1; i <= N; i++) { Pre[i] = Math.Min(X * i, Pre[i - 1] + A[i - 1]); Suff[i] = Math.Min(Y * i, Suff[i - 1] + A[N - i]); } // Calculating answer as the minimum of // all possible Pre[i]+Suff[N-i] for ( int i = 0; i <= N; i++) { answer = Math.Min(answer, Pre[i] + Suff[N - i]); } // Returning final answer return answer; } // Driver code public static void Main( string [] args) { int N = 5, X = 4, Y = 3; int [] A = { 5, 5, 0, 6, 3 }; // Function call int ans = MinimumSum(N, A, X, Y); Console.WriteLine(ans); } } |
Javascript
// Function to minimize the sum of the array by replacing // initial L elements with X and R elements from the end with Y function minimumSum(N, A, X, Y) { // Declaring 2 arrays Pre[] and Suff[] to // store the minimum possible sum of each // subarray from the beginning and end respectively const Pre = new Array(N + 1); const Suff = new Array(N + 1); Pre[0] = 0; Suff[0] = 0; // Initializing answer as a large value let answer = Infinity; // Iterating through 1 to N and calculating // the values of Pre and Suff for each index for (let i = 1; i <= N; i++) { Pre[i] = Math.min(X * i, Pre[i - 1] + A[i - 1]); Suff[i] = Math.min(Y * i, Suff[i - 1] + A[N - i]); } // Calculating the answer as the minimum of // all possible Pre[i] + Suff[N - i] for (let i = 0; i <= N; i++) { answer = Math.min(answer, Pre[i] + Suff[N - i]); } // Returning the final answer return answer; } // Driver code function main() { const N = 5; const X = 4; const Y = 3; const A = [5, 5, 0, 6, 3]; // Function call const ans = minimumSum(N, A, X, Y); console.log(ans); } // Invoke the driver code main(); |
14
Time Complexity: O(N)
Auxiliary Space: O(N)