Better complexity to problem 17.3?

#1

Hi I was working on some of the dynamic programming problems and I was wondering what you thought of the following solution for finding the combinations.

#include <iostream>
#include <vector>

using namespace std;

int find_combinations(int n, int k) {
   k = k > (n/2) ? n-k : k;
   vector<int> comb(k+1, 1);
   for(int i = 1; i < int(comb.size()); ++i) {
      comb[i] = (n * comb[i-1]) / i;
      n--;
   }
   return comb[k];
}

int main() {
   cout << find_combinations(50,6) << endl;
   return 0;
}

I believe this solution will run in O(k) time and space complexity. I am using the property of combinations where 9 choose 7 is equivalent to 9 choose 2 to keep the space complexity at O(k). For the time complexity if we analyze the combinations formula we have something like this:
For 9 choose 1 we have
9 / 1
For 9 choose 2 we have
(9 * 8) / (2 * 1) -> we can see that we already computed the 9/1 in the previous combination and use it instead.
And the same follows for 9 choose 3 and so on.
(9 * 8 * 7) / (3 * 2 * 1)

Let me know what you think about this solution!

Best,

Luis

0 Likes
#2

Hey Luis,

I think this algorithm is OK but there are two problems:

  1. Although the result will be fitted into a 32-bit integer but the intermediate result of your algorithm may not be fitted into a 32-bit integer, which will cause error. Besides, you are using an integer to store the intermediate result which may generate some fractional numbers during the computation.
  2. If you like to use this approach, you may not need a vector to store the intermediate results where a single variable should suffice.

Please let me know what you think about those comments.

0 Likes