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?


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 license header, choose License Headers in Project Properties.
  • 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)
    return 1;
    //fill red
    int x=0;
    // fill blue
    int y=0;

     return x+y;

    public static void main(String[] args) {
    Scanner sc=new Scanner(;
    int n=sc.nextInt();
    int m=sc.nextInt();
    int k=sc.nextInt();
    int ans=getans(n+m, n, m, k, k);



use memorization for better performance

which company this is asked?

DP is one of the solution but I think you can solve it using P&C.

If M and N both less than K ans is direct (M+N)!/ (M! * N!)
else if one of them is bigger than K ,say M ,
then consider k+1 Red candies to be together and consider them as a bunch,
now ,find the number of ways for this (Standard P & C), and subtract from total.

if both M and N are greater than K ,then bunch only K+1 reds first, subtract the number of ways from total,then only K+1 blues,subtract from total, then K+1 reds and K+1 blues together ,add to total.(Principle of inclusion and exclusion)

:star_struck: :star_struck: