Sum of different numbers in an array

Question

I want to have a function that returns the sum of different (non duplicate) values from an array: if I have {3, 3, 1, 5}, I want to have sum of 3 + 1 + 5 = 9.

My attempt was:

int sumdiff(int* t, int size){
    int sum=0;
    for (int i=0; i<=size;i++){
        for(int j=i; j<=size;j++){
            if(t[i]!=t[j])
            sum=sum+t[i];
        }
    }
    return sum;
}

int main()
{
    int t[4]={3, 3, 1, 5};
    cout << sumdiff(t, 4);
}

It returns 25 and I think I know why, but I do not know how to improve it. What should I change?

Answer 1

Put all the items in a set, then count them.

Sets are data structures that hold only one element of each value (i.e., each of their elements is unique; if you try to add the same value more than once, only one instance will be count).

You can take a look in this interesting question about the most elegant way of doing that for ints.

Answer 2

First of all, your loop should be for (int i=0; i<size;i++). Your actual code is accessing out of the bounds of the array.

Then, if you don't want to use STL containers and algorithms (but you should), you can modify your code as follows:

int sumdiff(int* t, int size){
    int sum=0;
    for (int i=0; i<size;i++){

        // check if the value was previously added

        bool should_sum = true;

        for(int j=0; should_sum && j<i;j++){
            if(t[i]==t[j])
                should_sum = false;
        }

        if(should_sum)
            sum=sum+t[i];
    }
    return sum;
}

int main()
{
    int t[4]={3, 3, 1, 5};
    cout << sumdiff(t, 4);
}

Answer 3

You could:

Store your array contents into an std::unordered_set first. By doing so, you'd essentially get rid of the duplicates automatically.

Then call std::accumulate to compute the sum

Answer 4

**wasthishelpful's answer was exactly what i was talking about. I saw his post after i posted mine.

So, you're trying to check the duplicate number using your inner loop. However, your outer loop will loop 4 times no matter what which gives you wrong result. Try,

• Do only checking in inner loop. (use a flag to record if false)
• Do your sum outside of inner loop. (do the sum when flag is true)

Answer 5

Insert array elements into a set and use the std::accumulate function:

#include <iostream>
#include <numeric>
#include <set>

int main()
{
    int t[4] = { 3, 3, 1, 5 };
    std::set<int> mySet(std::begin(t), std::end(t));
    int mySum = std::accumulate(mySet.begin(), mySet.end(), 0);
    std::cout << "The sum is: " << mySum << std::endl;
    return 0;
}

Answer 6

Here is another solution using std::accumulate, but it iterates over the original elements in the call to std::accumulate, and builds the set and keeps a running total as each number in the array is encountered:

#include <iostream>
#include <numeric>
#include <set>

int main()
{
    int t[4] = { 3, 3, 1, 5 };
    std::set<int> mySet;
    int mySum = std::accumulate(std::begin(t), std::end(t), 0, 
         [&](int n, int n2){return n += mySet.insert(n2).second?n2:0;});
    std::cout << "The sum is: " << mySum << std::endl;
    return 0;
}

The way it works is that std::insert() will return a pair tbat determines if the item was inserted. The second of the pair is a bool that denotes whether the item was inserted in the set. We only add onto the total if the insertion is successful, otherwise we add 0.

Live Example