# Adding two sides of an array

The purpose of the program is to add 2 sides of an array starting from the bottom and top of both ends and to find the lowest difference at equal decrements of iteration. The program functions but it's slow.

int solution(vector<int> &A) {
int n = A.size();
int i, j, rsum, lsum, difference;
int currentmindifference = 1000;

for(i = 0; i < n; i++)
{
lsum = 0;
rsum = 0;
for(j = 0; j <= i; j++) lsum += A[j];
for(j = i + 1; j < n; j++) rsum += A[j];
difference = abs (lsum - rsum);
if (difference < currentmindifference) currentmindifference = difference;
}

return currentmindifference;
}

-

Your code is $O(n^2)$. You can improve it to $O(n)$ by precomputing a sum array.

int solution(vector<int> &A) {
int n = A.size();
int i, j, rsum, lsum, difference;
int currentmindifference = 1000;

std::vector<int> pre(n);
pre[0] = A[0];
for (i = 1; i < n; i++)
pre[i] = pre[i - 1] + A[i];

for(i = 0; i < n; i++)
{
lsum = pre[i];
rsum = pre[A.size() - 1] - lsum;
difference = abs (lsum - rsum);
if (difference < currentmindifference) currentmindifference = difference;
}

return currentmindifference;
}


Reasoning. By calculating a sum array, we save the need to calculate lsum on each iteration. Furthermore, we notice that we can find rsum by finding the total sum less lsum.

We can simplify this further by noting that lsum and rsum are now superfluous. We will also replace 1000 with std::numeric_limits<int>::max() to ensure we get a true minimum instead of capping it, and check if A is empty before using it.

#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>

int solution(std::vector<int> &A) {
if (A.empty())
return -1; // or some other meaningful error value

int n = A.size();
int minDifference = std::numeric_limits<int>::max();

std::vector<int> pre(n);
pre[0] = A[0];
for (int i = 1; i < n; i++)
pre[i] = pre[i - 1] + A[i];

for (int i = 0; i < n; i++)
minDifference = std::min(minDifference, std::abs(2 * pre[i] - pre[n - 1]));

return minDifference;
}


Further reading: Prefix sum array and difference array. Disclosure: I am an administrator on this site. Excuse the formatting.

-
A word of warning: This code will crash if A is empty. – Aurelius Jul 24 '14 at 15:48
@Aurelius Good catch. Thank you. – Schism Jul 24 '14 at 16:22

-

# Coding Style

### Limit variable scope

It is best to limit the scope of your variables to the smallest scope possible. You aren't writing C89, so you don't need to declare variables at the top of the function.

### Naming

Be sure to give descriptive names to variables and function parameters. A is not descriptive. Also, it's good to denote separation between words in names. currentmindifference is hard to read. You should pick either camelCase or snake_case for variable names and be consistent.

### Use const where you can

If a variable is not supposed to be modified, it should be marked const. The compiler can then verify that the variable is never changed. Both n and A should be marked const.

# Algorithm

Inspired by Schism's linear-time solution, there are several opportunities to replace hand-written for loops with standard algorithms. These make the code easier to read and reason about. My implementation follows:

#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <limits>
#include <numeric>
#include <vector>

int solution(const std::vector<int>& values)
{
if (values.empty()) {return std::numeric_limits<int>::max();}

std::vector<int> partial, diffs;
std::partial_sum(values.begin(), values.end(), std::back_inserter(partial));
std::transform(partial.begin(), partial.end(), std::back_inserter(diffs), [&] (int x)
{
return std::abs(2 * x - partial.back());
});
const auto min = std::min_element(diffs.begin(), diffs.end());
return *min;
}


This consumes more memory than a hand-rolled loop because diffs needs to be filled with values. If memory is constrained, the calls to std::transform() and std::min_element() can be replaced with a hand-written loop.

-

Disclaimer : This part of the review does not review performances related issues.

Before anything, I'm assuming you are actually using std::vector and used using namespace std;. Using using namespace std; is usually considered a bad practice.

You can easily make your code cleaner by defining the local variables in the smallest possible scope. This can be done very easily :

int solution(std::vector<int> &A) {
int n = A.size();
int currentmindifference = 1000;

for(int i = 0; i < n; i++)
{
int lsum = 0;
int rsum = 0;
for(int j = 0; j <= i; j++) lsum += A[j];
for(int j = i + 1; j < n; j++) rsum += A[j];
int difference = abs (lsum - rsum);
if (difference < currentmindifference) currentmindifference = difference;
}

return currentmindifference;
}


Then, you can use std::min:

currentmindifference = std::min(difference, currentmindifference);


Then, you can use a single variable to handle the relative difference and call abs as you call std::min :

int solution(std::vector<int> &A) {
int n = A.size();
int currentmindifference = 1000;

for(int i = 0; i < n; i++)
{
int rel_diff = 0;
for(int j = 0; j <= i; j++)    rel_diff += A[j];
for(int j = i + 1; j < n; j++) rel_diff -= A[j];
currentmindifference = std::min(abs(rel_diff), currentmindifference);
}

return currentmindifference;
}


Now, to make your code more correct, you shouldn't assume 1000 will be the maximum : you can use int minDifference = std::numeric_limits<int>::max();.

As I was about to handle the performance part, I realised that @Schism has already said what I wanted to say (and probably in a better way).

-