Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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;
}
share|improve this question

4 Answers 4

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.

share|improve this answer
1  
A word of warning: This code will crash if A is empty. –  Aurelius Jul 24 at 15:48
    
@Aurelius Good catch. Thank you. –  Schism Jul 24 at 16:22
    
@Jamal TIL inline LaTeX on SE. Thanks. I tried $ to no avail, and $$ only got me display mode. –  Schism Jul 24 at 18:29
    
@Schism: I guess this isn't mentioned for CR specifically, but yeah, \$ is our MathJax delimiter. –  Jamal Jul 24 at 18:31
1  
This is an improvement, but there's a better algorithm. See my answer. –  Edward Jul 24 at 18:44

Your baseline code is a good starting point because it (mostly) works, but there are some things that could be improved.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid. I don't know that you've actually done that, (you might have used the slightly more enlightened using std::vector;) but it's an alarmingly common thing for new C++ programmers to do.

Avoid arbitrary "magic numbers"

The number 1000 in your code is somewhat suspect. Where did it come from? Why 1000 instead of 10000 or -9? It's better to declare some named const, or even better, use an already existing constant such as std::numeric_limits<int>::max().

Use const wherever you can

You could (and should) use const for the vector that you're passing to your routine, and you can also use it for n because it is only initialized once and never changed.

Consider generality where practical

The code currently only accepts a std::vector of int values and would require changes if it were used with, for example a std::vector of float values. Because this is a mechanism that would be appropriate for many different kinds of numeric values, consider using a templated class instead.

Consider your algorithm carefully

Other answers have provided alternate ways of doing the calculation, but require more memory. There is another way of doing this which is fairly simple. Consider your original code in which you have an lsum and rsum value at some arbitary point in the vector. If we consider the values \$l\$ and \$r\$ to be the lsum and rsum values and \$d\$ to be the value difference (without the absolute value), then advancing to the next array value \$i\$ and calculating \$l'\$ and \$r'\$ and \$d'\$ can be done like this: $$\begin{eqnarray} d &=& r - l \\ r' &=& r - i \\ l' &=& l + i \\ d' &=& r' - l' \\ &=& (r - i) - (l + i) \\ &=& r - i - l - i \\ &=& r - l - 2i \\ &=& d - 2i \end{eqnarray}$$

This result means that there is no need to store the lsum and rsum values, nor is there a need to create an additional vector of partial sums.

Try to use descriptive names

I didn't find much use in the name solution for the function. It may be accurate but it doesn't convey much meaning to other programmers. Consider that it's a minimum partial sum so maybe a better name would be minpsum? I'm not sure that's a huge improvement, but maybe you can come up with something better. Also A is arguably not a great name, but if we consider it to be short for Array than it's at least defendable.

Result

So we can effectively apply all of these ideas into a routine like this:

  template <typename T>
  T minpsum(const std::vector<T> &A) {
    if (A.empty()) {return std::numeric_limits<T>::max();}
    T posdiff{std::accumulate(A.cbegin(), A.cend(), T(0))};
    const T zero{0};
    T diff=posdiff;
    T negdiff{-posdiff};
    if (posdiff < zero)
      std::swap(negdiff, posdiff);
    for (const auto &i : A) {
      diff -= (i+i);
      if (diff < zero && diff > negdiff) {
        negdiff = diff;
      } else if (diff > zero && diff < posdiff) {
        posdiff = diff;
      }
    }
    negdiff = -negdiff;
    return posdiff < negdiff ? posdiff : negdiff;
  }

As you can see, there is no longer a call to abs because that would assume int arguments and I wanted to make the code generic, accepting float or double or whatever as a templated function. I have also used the C++11 range operator and std::accumulate with const iterators. We can try it out with the following driver code:

  int main()
  {
    std::vector<int> vec(1000);
    std::iota(vec.begin(), vec.end(), -200);
    int s = minpsum(vec);
    std::cout << s << '\n';
    assert(s == 394);
  }

This version of the code will work with the fundamental math types but not with something like std::complex<std::double> because the latter type does not implement the comparison operators < and > which are required by this code.

Limitations

It should be noted that there is a chance of overflow or numeric wraparound when this code is used. The assumption made in the code is that the type T is sufficient to not only hold each member of the array, but also the sum of all of them, which may or may not be valid.

Also, because of the subtraction, there is the potential for unsigned numbers to "wrap" around 0. That is, \$3 - 5 = -2\$, but \$-2\$ is not representable as an unsigned number. Caveat lector.

share|improve this answer

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.

share|improve this answer

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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.