Show problems as
Classic problem #2929MediumMathCombinatoricsEnumeration

Distribute Candies Among Children II

Real-world version: Splitting a Batch Across Three Bins
Tracked in this browser only
Read Distribute Candies Among Children II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A batch of n identical parts is to be split across three bins, taken in order, and no bin may hold more than cap parts. A bin may be left empty.

Two splits count as different when some bin's count differs between them. Return how many splits there are.

Examples

Example 1

Input
n = 5, cap = 2
Output
3

Five parts across three bins holding at most two each. The counts have to be some ordering of two, two and one, and there are three places the single part can go.

Example 2

Input
n = 3, cap = 3
Output
10

Three parts with a cap of three means the cap never bites, so every way of writing three as an ordered triple counts: all in one bin, three ways; two and one, six ways; and one each, one way.

Example 3

Input
n = 10, cap = 2
Output
0

Three bins of at most two hold six parts between them, which is short of ten, so no split works.

Constraints

  • 1 <= n <= 10^6
  • 1 <= cap <= 10^6

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def distribute_candies(n: int, cap: int) -> int:
Java
public long distributeCandies(int n, int cap)

More on the same topics