CODEWITHSUNDEEP
c++arrayssumsubset-sum
user103572
user103572

Reputation: 489

Find the elements of an array based on minimum sum

I've written a loop in C++ to give me 6 random numbers and store them in an array. What I would like to do is to sum the elements of the array until I get a value larger than a number, "x", but I would like to do this without necessarily adding all the elements. The objective is to find the first elements which sum to the value of x.

For example, array is [1,2,3,4,5,6], and x = 6, so what I would be looking for are the elements [1,2,3].

I've looked at the standard library and have tried using the sum function from "valarray" but this just gives the sum of all the elements. Any ideas on how to code this successfully would be greatly appreciated.

Upvotes: 4

Views: 2942

Answers (9)

Tom
Tom

Reputation: 45104

Well, i would use a vector 

T addUntil(T array[],size_t len,T thres){
    vector<T> vec = vector_from_array(array,len)
    T sum;
    for (size_t i=0;i< vec.size(),sum<thresh;i++){
          sum+= vec[i];
    }
    return sum;
}

T would need operator+ and operator< to be defined.

Upvotes: 0

Daniel Daranas
Daniel Daranas

Reputation: 22624

Substract the numbers from x one by one, until you reach 0 or lower.

No additions, as you wished :)

Upvotes: 2

Viktor Sehr
Viktor Sehr

Reputation: 13099

would be something like:

struct StopAtValue{
  StopAtValue(int sum) : m_sum(sum), m_accumulated(0){}
  bool operator()(int val){
    m_accumulated += val;
    return m_accumulated >= sum;
  }
  int m_sum;
  int m_accumulated;
}


int* pos = std::find_if(&array[0], &array[n], StopAtValue(6));

Upvotes: 0

Ben Hymers
Ben Hymers

Reputation: 26526

Avoid the answers that suggest using find_if with a stateful predicate. Stateful predicates are dangerous as the STL algorithms assume it is safe to copy predicates. In this case, if copies are made of the predicate then each will have a different 'running total' and will not necessarily act on all values, or in the correct order.

Especially avoid the solution that implements its predicate's operator() member as a const member function but labels its members as mutable as this is fooling you into thinking it is not a stateful predicate, which is bad.

I'd suggest using either one of the answers that simply loops to find the answer, or the answer that uses an accumulator, as that is the most correct way to do it (even if the code looks a little unwieldy.

Note that the warnings may well not apply to C arrays and find_if; I just don't want you to learn that stateful predicates are the right way to solve your problem since you may end up using that incorrect solution in a situation where it is dangerous in future.

Reference: C++ Coding Standards: 101 Rules, Guidelines, and Best Practices, Item 87

Upvotes: 3

encee
encee

Reputation: 4664

Here's hoping this works:

/* Returns an index i, given array valarray[0,1..n] and number x where i is an index to valarry such that sum over j of valarray[j] for j = 0 to i > x */
int getFirstSum(int *valarray, int n, int x)
{
   int i = 0;
   int sum = x;
   while(sum > x && i < n)
   {
      i++;
      sum -= valarray[i];
   }
   return i;
}

Upvotes: 0

dirkgently
dirkgently

Reputation: 111130

Here's a slightly more generic version:

#include <iostream>
#include <algorithm>

// return an iterator _Last such that sum 
// of all elements in the range [_First, _Last)
// satisfies the predicate Func
template<class InIt,
class Ty,
class Fn> inline
InIt accumulate_if(InIt First, InIt Last, Ty Val, Fn Func)
{   
    for (; Func(Val) && First != Last; ++First)
        Val = Val + *First;
    return (First);
}

int main() {
    int num[] = {1, 2, 3, 4, 5, 6};
    int *last = accumulate_if(num, num + sizeof num / sizeof num[ 0 ], 
                              0, std::bind2nd(std::less<int>(), 6));
    std::copy(num, last, std::ostream_iterator<int>(std::cout, "\n"));
    return 0;
}

Upvotes: 2

Loki Astari
Loki Astari

Reputation: 264381

Write a functor that does the addition.

#include <algorithm>
struct SumToo
{
     SumToo(int val):m_val(val),m_sum(0) {}
     int m_val;
     int m_sum;

     bool operator()(int next)
     {
         m_sum += next;
         return m_sum >= m_val;
     }
 };

 int main()
 {
       int data[] = {1,2,3,4,5,6};

       int* find = std::find_if(data,data+6,SumToo(6));
 }

Upvotes: 13

John Dibling
John Dibling

Reputation: 101456

You could use std::find_if() along with a functor that maintains a running total, and only returtn true from the functor when you have found the element that puts you at or over the top.

For example:

#include <cstdlib>
#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
using namespace std;

// functor returns true when the running total >= findVal
struct running_total : public unary_function<int, bool>
{
    running_total(int findVal) : findVal_(findVal), runningTtl_(0) {};
    bool operator()(int rhs) const
    {
        runningTtl_ += rhs;
        if( runningTtl_ >= findVal_ )
            return true;
        else
            return false;
    }
private:
    mutable int runningTtl_;
    const int findVal_;
};

int main()
{

    int nums[] = {1, 2, 3, 4, 5, 6};
    size_t count = sizeof(nums)/sizeof(nums[0]);

    const int scanTtl = 6;  // running total to scan to
    int * pos = find_if(&nums[0], &nums[0]+count, running_total(scanTtl));

    cout << "Elements Totaling " << scanTtl << " : ";
    copy(&nums[0], pos+1, ostream_iterator<int>(cout, ", "));

    return 0;
}

Upvotes: -1

Matt Dillard
Matt Dillard

Reputation: 14853

I'm assuming you just want the first X elements in the array, up until their sum meets or exceeds a threshold (the question was a little vague there).

If so, I don't know how to do that without your own loop:

int sum = 0;
int i = 0;
for( ; i < len; ++i ) {
    sum += array[i];
    if( sum >= 6 ) {
        break;
    }
}

Now "i" contains the index at which the sum met or exceeded your threshold.

Upvotes: 8

Related Questions