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
Problem: Special Sum
Problem Link: www.codingninjas.com/codestudio/problems/special-sum_1281320
Approach:
Calculate the cumulative sum of the array.
Initiate a variable last = n-1 (From the backward direction)
For each i, calculate cumulative_sum[i] + cumulative_sum[n-1] - cumulative_sum[last]. Reduce last by 1.
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;
}