hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Special Sum


  • Approach:

    1. Calculate the cumulative sum of the array.

    2. Initiate a variable last = n-1 (From the backward direction)

    3. For each i, calculate cumulative_sum[i] + cumulative_sum[n-1] - cumulative_sum[last]. Reduce last by 1.

    4. Take the minimum between the currently calculated sum and the previously calculated sum.


  • Time and Space Complexity:

      • Time Complexity: O(N)

      • Space Complexity: O(N)


Code [C++]

#include <bits/stdc++.h>

int specialSum(vector<int> &arr, int n)

{

vector<int>cumSum(n, 0);

cumSum[0] = arr[0];

for(int i=1; i<n; i++) cumSum[i] = cumSum[i-1] + arr[i];

int last = n - 1;

int minSum = INT_MAX;

for(int i=0; i<n; i++){

int sumValue = cumSum[i] + (cumSum[n-1] - (((last-1) < 0) ? 0 :cumSum[last-1]));

minSum = min(minSum, sumValue);

last--;

}

return minSum;

}