2928

2928. Distribute Candies Among Children I (Easy)

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.

 

Example 1:

Input: n = 5, limit = 2
Output: 3
Explanation: There are 3 ways to distribute 5 candies such that no child gets more than 2 candies: (1, 2, 2), (2, 1, 2) and (2, 2, 1).

Example 2:

Input: n = 3, limit = 3
Output: 10
Explanation: There are 10 ways to distribute 3 candies such that no child gets more than 3 candies: (0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0) and (3, 0, 0).

 

Constraints:

• 1 <= n <= 50
• 1 <= limit <= 50

Companies: Amazon, Rubrik

Related Topics:
Math, Combinatorics, Enumeration

Similar Questions:

• Count Ways to Distribute Candies (Hard)

Hints:

• Use three nested for loops to check all the triplets.

Solution 1.

// OJ: https://leetcode.com/problems/distribute-candies-among-children-i
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int distributeCandies(int n, int limit) {
        int ans = 0;
        for (int i = 0; i <= limit; ++i) {
            ans += max(0, min(n - i, limit) - max(0, n - i - limit) + 1);
        }
        return ans;
    }
};

Discuss

https://leetcode.com/problems/distribute-candies-among-children-i/solutions/4301078/c-o-n-time-one-pass/