Solutions

1. Brute Force

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        res = 0
        for a in range(limit + 1):
            for b in range(limit + 1):
                for c in range(limit + 1):
                    if a + b + c == n:
                        res += 1
        return res

Time & Space Complexity

Time complexity: $O(l ^ 3)$
Space complexity: $O(1)$

Where $l$ is the given limit.

2. Better Approach

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        res = 0
        for a in range(min(n, limit) + 1):
            for b in range(min(n - a, limit) + 1):
                if n - a - b <= limit:
                    res += 1
        return res

Time & Space Complexity

Time complexity: $O(min(n, limit) ^ 2)$
Space complexity: $O(1)$

3. Enumeration - I

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        res = 0
        for a in range(min(n, limit) + 1):
            b_max = min(n - a, limit)
            b_min = max(0, n - a - limit)
            if b_max >= b_min:
                res += b_max - b_min + 1
        return res

Time & Space Complexity

Time complexity: $O(min(n, limit))$
Space complexity: $O(1)$

4. Enumeration - II

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        res = 0
        for a in range(min(n, limit) + 1):
            if n - a <= 2 * limit:
                res += min(n - a, limit) - max(0, n - a - limit) + 1
        return res

Time & Space Complexity

Time complexity: $O(min(n, limit))$
Space complexity: $O(1)$

5. Inclusion-Exclusion Principle

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        C3 = [1, 3, 3, 1]
        res = 0
        for j in range(4):
            m = n - j * (limit + 1)
            if m < 0:
                continue
            ways = (m + 2) * (m + 1) // 2
            sign = -1 if j % 2 else 1
            res += sign * C3[j] * ways
        return res

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$