 # Coding question asked in my placement

You are given N red pieces of candy and M blue pieces of candy. Write a program to find the number of arrangements of candy in which not more than K pieces of the same color are placed next to each other.
Sample test case-
Input format = N M K
Input = 1 1 1 (Output = 2) (Explanation = possible combinations are RB BR which satisfies above condition)
Input = 2 1 1 (Output = 1) (Explanation = possible combinations are RRB RBR BRR but only RBR satisfies above condition)

Anyone pls help how to do this?

2 Likes

its a dp problem

in this problem you have to use dynamic programming
when you fill red candies then the number of blue candies that will we can fill next will reset to k
same for blue candies
i use recursive dp and my code is below for better understanding

Dont throw his question out of da window like that : ( :facepalm

/*

• To change this template file, choose Tools | Templates
• and open the template in the editor.
*/
package candies;

import java.util.Scanner;

/**
*

• @author Abhinav Vijayvargiya
*/
public class Candies {

static int limit_red=0;
static int limit_blue=0;
static int getans(int total,int red,int blue,int r,int b)
{
if((red+blue)==0)
{
return 1;
}
//fill red
int x=0;
if(red>0&&r>0)
{
x=getans(total-1,red-1,blue,r-1,limit_blue);
}
// fill blue
int y=0;
if(blue>0&&b>0)
{
y=getans(total-1,red,blue-1,limit_red,b-1);

`````` }
return x+y;
``````

}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
int k=sc.nextInt();
limit_blue=k;
limit_red=k;
int ans=getans(n+m, n, m, k, k);
System.out.println(ans);

}

}

use memorization for better performance  