Expert: Zlatko - 6/11/2010

Question
Hello Zlatko,
I want to have a program that counts the number of vectors like (X1 , X2 , … , Xn) subject to :
Sum of Xi  = r    (summation upon i=1,…,n )
&
X(i) >=X(i+1)    for i=1,…,n-1
For example for n=4 and r=6 the program should counts the vector (3,2,1,0) but it shouldn't counts (3,2,0,1).
Can you help me?

Answer
Hello Amir.

Nice to hear from you again.

So, you want to count the number of vectors whose elements sum to r, and which are sorted in descending order. Is that correct ? I assume that these are C++ std::vector vectors. Even if it is an array, the idea is the same. You must go through each element, checking that it is >= the previous, and calculating the sum. Here are 2 functions, one with std::vector, one with an array.

#include <vector>
using namespace std;


bool isVectorGood(const vector<int>& v, int r)
{
   int sum = v[0];
   for(int ix = 1; ix < (int)v.size(); ++ix)
   {
       if (v[ix] > v[ix-1] || sum > r) return false;
       sum += v[ix];
   }
   return sum == r;
}

bool isVectorGood(int* v, int size, int r)
{
   int sum = v[0];
   for(int ix = 1; ix < size; ++ix)
   {
       if (v[ix] > v[ix-1] || sum > r) return false;
       sum += v[ix];
   }
   return sum == r;
}

So in your program, call isVectorGood for each of your vectors, and count the number of true results. You can probably think of a better name for the function.

Does that help ?

Best regards
Zlatko