2929. Distribute Candies Among Children II

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 <= 106
• 1 <= limit <= 106

Approach 01:

class Solution {
public:
    long long distributeCandies(int totalCandies, int maxCandiesPerChild) {
        const int limitPlusOne = maxCandiesPerChild + 1;
        const long oneChildOverLimit = countWays(totalCandies - limitPlusOne);
        const long twoChildrenOverLimit = countWays(totalCandies - 2 * limitPlusOne);
        const long threeChildrenOverLimit = countWays(totalCandies - 3 * limitPlusOne);
        return countWays(totalCandies) - 3 * oneChildOverLimit + 3 * twoChildrenOverLimit - threeChildrenOverLimit;
    }
private:
    long countWays(int candies) {
        if (candies < 0){
            return 0;
        }            
        return computeCombination(candies + 2, 2);  
    }
    long computeCombination(int n, int k) {
        long result = 1;
        for (int i = 1; i <= k; ++i){
            result = result * (n - i + 1) / i;
        }            
        return result;
    }
};

class Solution:
    def distributeCandies(self, totalCandies: int, maxCandiesPerChild: int) -> int:
        limitPlusOne = maxCandiesPerChild + 1
        oneChildOverLimit = self.countWays(totalCandies - limitPlusOne)
        twoChildrenOverLimit = self.countWays(totalCandies - 2 * limitPlusOne)
        threeChildrenOverLimit = self.countWays(totalCandies - 3 * limitPlusOne)
        return (self.countWays(totalCandies) - 3 * oneChildOverLimit + 3 * twoChildrenOverLimit - threeChildrenOverLimit)
    def countWays(self, candies: int) -> int:
        if candies < 0:
            return 0
        return self.computeCombination(candies + 2, 2)  
    def computeCombination(self, n: int, k: int) -> int:
        result = 1
        for i in range(1, k + 1):
            result = result * (n - i + 1) // i
        return result

Time Complexity:

• distributeCandies function:

  Calls countWays four times, each involving computeCombination.

• computeCombination(n, 2):

  Runs a loop of size 2 → \(O(1)\) for each call.

• Total Time Complexity:

  \(O(1)\).

Space Complexity:

• Only uses constant extra space for variables and no recursion or dynamic allocation.
• Total Space Complexity:

  \(O(1)\).