Distribute Candies Among Children II

My original set-up was an O(limit) solution, where you iterated from 0 to limit inclusive.

That would represent the candies one of the children would receive. We then check for the largest amount of candies we can distribute to one of the remaining children. It is the minimum value between:

• limit, as that is the maximum amount of candies that a child can receive
• n - i, which is the total minus the candies the first child received
  • this is because we can set the a child to receive 0 candies, so the last one would receive n-i candies

Then, after finding the largest amount of candies we can distribute to one of the remaining children, we can hence calculate the minimum amount of candies we can distribute to the last child.

As long as the minimum that we calculate is smaller than or equal to the maximum, we can add the difference between the two + 1 to find the total number of configurations we can form (if the first child gets i candies).

An example, for n = 6 and limit = 6, if we have i = 1, then:

• minimum difference = 0
• maximum difference = 5

so we can form 6 configurations:

1. 1, 0, 5
2. 1, 1, 4
3. 1, 2, 3
4. 1, 4, 2
5. 1, 4, 1
6. 1, 5, 0

code

class Solution {
public:
    long long distributeCandies(int n, int limit) {
        if (limit*3 < n) {
            return 0;
        } else {
            long long ans = 0;
            for (int i = 0; i <= limit; ++i) {
                int difference = min(n-i, limit);
                if (n-i-difference <= difference) {
                    ans += (2*difference+i-n)+1;
                }
            }
            return ans;
        }
    }
};

complexity

• Time: O(n)
• Space: O(1)

Note, there does exist a math solution to this problem, using the inclusion and exclusion property.

Basically, you can use permutations and combinations to calculate:

• total number of ways of distributing n candies to 3 children (1 possible arrangement)
• total number of ways of distributing n candies to 3 children BUT 1 child has limit+1 candies already (3 possible arrangements)
• total number of ways of distributing n candies to 3 children BUT 2 children has limit+1 candies already (3 possible arrangements)
• total number of ways of distributing n candies to 3 children BUT 3 children has limit+1 candies already (1 possible arrangement)

Since there is overlap between all the sets, using the inclusion and exclusion property, we can effectively calculate the answer in O(1) time:

complexity

• Time: O(1)
• Space: O(1)