Which is better way to calculate nCr

0 votes

Approach 1:
C(n,r) = n!/(n-r)!r!

Approach 2: 

I discovered this in Wilf's book Combinatorial Algorithms: C(n,r) may be represented as C(n-1,r) + C (n-1,r-1).

e.g.

C(7,4) = C(6,4) + C(6,3) 
       = C(5,4) + C(5,3) + C(5,3) + C(5,2)
       .   .
       .   .
       .   .
       .   .
       After solving
       = C(4,4) + C(4,1) + 3*C(3,3) + 3*C(3,1) + 6*C(2,1) + 6*C(2,2)

As you can see, there is no need for multiplication in the final result. 

In every C(n,r) form, either n==r or r==1.

Here is an example of the code I used:

int foo(int n,int r)
{
     if(n==r) return 1;
     if(r==1) return n;
     return foo(n-1,r) + foo(n-1,r-1);
}

Approach 2 has overlapping sub-problems where we use recursion to tackle the same sub-problems again. 

Using Dynamic Programming, we can prevent this.

Which method is preferable for calculating C(n,r)?

Jul 25 in C++ by Nicholas
• 5,020 points
10 views

No answer to this question. Be the first to respond.

Your answer

Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.

Related Questions In C++

0 votes
1 answer

What is the best way to use a HashMap in C++?

The ordered and unordered map containers (std::map and std::unordered map) are included in the standard library.  The items in an ordered map are sorted by key, and insert and access are in O (log n).  For ordered maps, the standard library often use red black trees.  However, this is only an implementation detail.  Insert and access are in O in an unordered map (1).  It is simply another term for a hashtable. An illustration using (ordered) std::map: #include <map> #include <iostream> #include <cassert> int main(int argc, char ...READ MORE

answered Jun 10 in C++ by Damon
• 4,960 points
44 views
0 votes
0 answers

What is the easiest way to initialize a std::vector with hardcoded elements?

I can make an array and initialise&nb ...READ MORE

Jun 27 in C++ by Nicholas
• 5,020 points
24 views
0 votes
1 answer

Is there an easy way to make a min heap in C++?

Use make heap() and its buddies from algorithm>, or priority queue from queue>.  Make heap and friends are used by priority queue. #include <queue> // functional,iostream,ctime,cstdlib using namespace std; int main(int ...READ MORE

answered Jun 27 in C++ by Damon
• 4,960 points
23 views
0 votes
0 answers

What is the fastest way to transpose a matrix in C++?

I have a reasonably large matrix that I need to transpose.  Assume, for example, that my matrix is a b c d e f g h ...READ MORE

Jul 15 in C++ by Nicholas
• 5,020 points
10 views
0 votes
0 answers

Visual C++ vs Visual C# , which is the best to learn?

I completed my C++ lessons and practises ...READ MORE

Jul 22 in C++ by Nicholas
• 5,020 points
13 views
0 votes
0 answers

What is the difference between cout, cerr, clog of iostream header in c++? When to use which one?

I looked up the differences between cout, ...READ MORE

Jul 27 in C++ by Nicholas
• 5,020 points
7 views
0 votes
1 answer

Why would anyone use set instead of unordered_set?

Unordered sets must compensate for their O(1) ...READ MORE

answered Jun 1 in C++ by Damon
• 4,960 points
54 views
0 votes
1 answer

Ternary operator ?: vs if...else

It's not any faster.  There is one difference when you can initialize a constant variable using an expression: const int x = (a<b) ? b ...READ MORE

answered Jun 7 in C++ by Damon
• 4,960 points
29 views
0 votes
1 answer

What is the difference between std::__gcd and std::gcd?

I done some research about this. The ...READ MORE

answered Jun 10 in C++ by Damon
• 4,960 points
48 views
0 votes
0 answers

Best way to reverse a string

I recently had to develop a string ...READ MORE

Jun 11 in C# by krishna
• 2,540 points
10 views
webinar REGISTER FOR FREE WEBINAR X
Send OTP
REGISTER NOW
webinar_success Thank you for registering Join Edureka Meetup community for 100+ Free Webinars each month JOIN MEETUP GROUP