Minimize Array sum by replacing L and R elements from both end with X and Y | By The Digital Insider

on

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++

#include <bits/stdc++.h>

using namespace std;

  

int minimumSum(int N, int A[], int X, int Y)

    

    

    

    int Pre[N + 1];

    int Suff[N + 1];

    Pre[0] = 0, Suff[0] = 0;

  

    

    int answer = INT_MAX;

  

    

    

    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]);

    

  

    

    

    for (int i = 0; i <= N; i++)

        answer = min(answer, Pre[i] + Suff[N - i]);

    

  

    

    return answer;

  

int main()

    int N = 5, X = 4, Y = 3;

    int A[] = 5, 5, 0, 6, 3 ;

  

    

    int ans = minimumSum(N, A, X, Y);

    cout << ans;

  

    return 0;

Time Complexity: O(N)
Auxiliary Space: O(N)



#Approach, #Arrays, #Code, #Container, #DSA, #Explanation, #Greedy, #Namespace, #Prefix, #PrefixSum, #R, #Read, #Responsive, #Solve, #Space, #Table, #Time, #TimeComplexity
Published on The Digital Insider at https://bit.ly/3lZ4Hhu.

Comments

Post a Comment

Comments are moderated.