2928. Distribute Candies Among Children I LeetCode Solution
In this guide, you will get 2928. Distribute Candies Among Children I LeetCode Solution with the best time and space complexity. The solution to Distribute Candies Among Children I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Distribute Candies Among Children I
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
Complexity Analysis
Time Complexity: O(1)
Space Complexity: O(1)
2928. Distribute Candies Among Children I LeetCode Solution in C++
class Solution {
public:
// Same as 2927. Distribute Candies Among Children III
int distributeCandies(int n, int limit) {
const int limitPlusOne = limit + 1;
const int oneChildExceedsLimit = ways(n - limitPlusOne);
const int twoChildrenExceedLimit = ways(n - 2 * limitPlusOne);
const int threeChildrenExceedLimit = ways(n - 3 * limitPlusOne);
// Principle of Inclusion-Exclusion (PIE)
return ways(n) - 3 * oneChildExceedsLimit + 3 * twoChildrenExceedLimit -
threeChildrenExceedLimit;
}
private:
// Returns the number of ways to distribute n candies to 3 children.
int ways(int n) {
if (n < 0)
return 0;
// Stars and bars method:
// e.g. '**|**|*' means to distribute 5 candies to 3 children, where
// stars (*) := candies and bars (|) := dividers between children.
return nCk(n + 2, 2);
}
int nCk(int n, int k) {
int res = 1;
for (int i = 1; i <= k; ++i)
res = res * (n - i + 1) / i;
return res;
}
}; /* code provided by PROGIEZ */
2928. Distribute Candies Among Children I LeetCode Solution in Java
class Solution {
// Returns the number of ways to distribute n candies to 3 children.
public int distributeCandies(int n, int limit) {
final int limitPlusOne = limit + 1;
final int oneChildExceedsLimit = ways(n - limitPlusOne);
final int twoChildrenExceedLimit = ways(n - 2 * limitPlusOne);
final int threeChildrenExceedLimit = ways(n - 3 * limitPlusOne);
// Principle of Inclusion-Exclusion (PIE)
return ways(n) - 3 * oneChildExceedsLimit + 3 * twoChildrenExceedLimit -
threeChildrenExceedLimit;
}
private int ways(int n) {
if (n < 0)
return 0;
// Stars and bars method:
// e.g. '**|**|*' means to distribute 5 candies to 3 children, where
// stars (*) := candies and bars (|) := dividers between children.
return nCk(n + 2, 2);
}
private int nCk(int n, int k) {
int res = 1;
for (int i = 1; i <= k; ++i)
res = res * (n - i + 1) / i;
return res;
}
} // code provided by PROGIEZ
2928. Distribute Candies Among Children I LeetCode Solution in Python
class Solution:
def distributeCandies(self, n: int, limit: int) -> int:
def ways(n: int) -> int:
"""Returns the number of ways to distribute n candies to 3 children."""
if n < 0:
return 0
# Stars and bars method:
# e.g. '**|**|*' means to distribute 5 candies to 3 children, where
# stars (*) := candies and bars (|) := dividers between children.
return math.comb(n + 2, 2)
limitPlusOne = limit + 1
oneChildExceedsLimit = ways(n - limitPlusOne)
twoChildrenExceedLimit = ways(n - 2 * limitPlusOne)
threeChildrenExceedLimit = ways(n - 3 * limitPlusOne)
# Principle of Inclusion-Exclusion (PIE)
return (ways(n)
- 3 * oneChildExceedsLimit
+ 3 * twoChildrenExceedLimit
- threeChildrenExceedLimit) # code by PROGIEZ
