Distribute Candies Among Children II - Practice Coding Problems

Distribute Candies Among Children II - Problem

You are given two positive integers n and limit. Return the total number of ways to distribute n candies among 3 children such that no child gets more than limit candies.

Each distribution must assign a non-negative number of candies to each child, and the sum of all candies distributed must equal n.

Input & Output

Example 1 — Basic Case

$ Input: n = 5, limit = 2

› Output: 3

💡 Note: The 3 ways are: (0,2,3) - invalid since 3>2, (1,1,3) - invalid, (1,2,2), (2,1,2), (2,2,1). Only 3 valid distributions: (1,2,2), (2,1,2), (2,2,1).

Example 2 — Small Input

$ Input: n = 3, limit = 3

› Output: 10

💡 Note: All possible distributions are valid since limit=3 ≥ n=3. Total ways = C(3+2,2) = C(5,2) = 10.

Example 3 — Tight Constraint

$ Input: n = 2, limit = 1

› Output: 3

💡 Note: Valid ways: (0,1,1), (1,0,1), (1,1,0). Each child gets at most 1 candy and total is 2.

Constraints

1 ≤ n ≤ 50
1 ≤ limit ≤ 50

Visualization

Tap to expand

Understanding the Visualization

Input

n=5 candies, limit=2 per child

Process

Find all valid distributions (x,y,z) where x+y+z=5 and x,y,z≤2

Output

Count = 3 valid ways

Key Takeaway

🎯 Key Insight: Use combinatorics to count distributions efficiently instead of enumeration

Asked in

G Google 15 a Amazon 12 M Microsoft 8

Brief HTML summary: The key insight is to use combinatorics with inclusion-exclusion principle. Count total ways using stars and bars, then subtract invalid distributions. Best approach is mathematical formula with Time: O(1), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Enumeration	O(limit²)	O(1)	Try all possible distributions and count valid ones
Mathematical Formula (Stars and Bars)	O(1)	O(1)	Use combinatorial formula to count distributions directly

Brute Force Enumeration — Algorithm Steps

Iterate child1 candies from 0 to min(n, limit)
Iterate child2 candies from 0 to min(n-child1, limit)
Calculate child3 = n - child1 - child2
Check if child3 <= limit and count valid cases

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Child1

Give 0 to limit candies to first child

Try Child2

For each Child1, try 0 to limit for second child

Check Child3

Calculate remaining candies and check if valid

Code -

solution.c — C

#include <stdio.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(int n, int limit) {
    int count = 0;
    for (int child1 = 0; child1 <= min(n, limit); child1++) {
        for (int child2 = 0; child2 <= min(n - child1, limit); child2++) {
            int child3 = n - child1 - child2;
            if (child3 >= 0 && child3 <= limit) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    int n, limit;
    scanf("%d %d", &n, &limit);
    printf("%d\n", solution(n, limit));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(limit²)

Two nested loops, each running up to limit times

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables for counting

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

345 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler