 # Program to find different ways to remove the balls

In a bag, there are n identical balls (n >= 1) that needs to be removed from the bag. You can either remove one ball or two balls at a time. Write a code that, given n, calculates how many different ways you can remove the balls from the bag. Example: n = 3, result = 31 - 1 - 1, 1 - 2, 2 - 1

In a bag, there are n identical balls (n >= 1) that needs to be removed from the bag. You can either remove one ball or two balls at a time. Write a code that, given n, calculates how many different ways you can remove the balls from the bag. Example: n = 3, result = 31 - 1 - 1, 1 - 2, 2 - 1

seems, It’s a DP. It’s basically the Fibonacci series.
F(n)=F(n-1)+F(n-2)
F(n)= number of ways to select n balls
F(n-1)= after you pick 1 ball
F(n-2)=after you pick 2 balls
Since, you can eithre pick 1 ball or 2 ball at a go
F(n)=F(n-1)+F(n-2) which is the fibonacci series
F(0)=1
F(1)=1
F(2)=2
F(3)=3
so on.
Hope you know how to find Fibonacci series. Else, check out our website
I am also adding the code-snippet

``````int F[n]={0};
//base  cases
F=1;
F =1;

for(int i=2;i<=n;i++){
F=F[i-1]+F[i-2];
}
``````

P.S: I haven’t compiled the code, just for your understanding. Thanks!

If you had founded solution already, would like to ask you to solve for a extended problem where you can pick at most m(m<=n) balls a time. Let’s understand the DP truly.

Thank you very much

1 Like