#1467

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Probability of a Two Boxes Having The Same Number of Distinct Balls

Compute the probability that two boxes contain the same number of distinct balls using careful combinatorial and DP methods.

array math dynamic programming backtracking combinatorics

Problem Statement

You are given an integer array balls where balls[i] represents the number of balls of the i-th color. The total number of balls is even. All balls are shuffled randomly and then divided equally into two distinct boxes, each containing half of the total balls.

Return the probability that both boxes end up containing the same number of distinct colors. Remember that boxes are distinct, so [color1] in box1 and [color2] in box2 is considered different from [color2] in box1 and [color1] in box2, even if the counts are equal.

Examples

Example 1

Input: balls = [1,1]

Output: 1.00000

Only 2 ways to divide the balls equally:

A ball of color 1 to box 1 and a ball of color 2 to box 2
A ball of color 2 to box 1 and a ball of color 1 to box 2 In both ways, the number of distinct colors in each box is equal. The probability is 2/2 = 1

Example 2

Input: balls = [2,1,1]

Output: 0.66667

We have the set of balls [1, 1, 2, 3] This set of balls will be shuffled randomly and we may have one of the 12 distinct shuffles with equal probability (i.e. 1/12): [1,1 / 2,3], [1,1 / 3,2], [1,2 / 1,3], [1,2 / 3,1], [1,3 / 1,2], [1,3 / 2,1], [2,1 / 1,3], [2,1 / 3,1], [2,3 / 1,1], [3,1 / 1,2], [3,1 / 2,1], [3,2 / 1,1] After that, we add the first two balls to the first box and the second two balls to the second box. We can see that 8 of these 12 possible random distributions have the same number of distinct colors of balls in each box. Probability is 8/12 = 0.66667

Example 3

Input: balls = [1,2,1,2]

Output: 0.60000

The set of balls is [1, 2, 2, 3, 4, 4]. It is hard to display all the 180 possible random shuffles of this set but it is easy to check that 108 of them will have the same number of distinct colors in each box. Probability = 108 / 180 = 0.6

Constraints

1 <= balls.length <= 8
1 <= balls[i] <= 6
sum(balls) is even.

Solution Approach

Use backtracking to explore all distributions

Recursively assign balls of each color to either box while maintaining counts. Track the number of balls and distinct colors in both boxes. Only consider paths where the total number of balls in each box is half of the total. Count valid distributions where the distinct color count is equal.

Apply state transition dynamic programming

Use a DP table indexed by current color index, balls in the first box, and difference in distinct counts. For each color, consider all ways to distribute its balls between the two boxes and update DP states accordingly. This approach avoids recomputation and scales better than naive recursion for multiple colors and balls.

Compute probability from counted configurations

After enumerating all valid distributions, divide the number of configurations with equal distinct counts by the total number of possible distributions. Factorial-based combinatorial formulas handle permutations of identical balls efficiently to get precise probability.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity depend on the number of colors k and maximum balls per color. Using DP reduces exponential exploration but requires O(k * n * n) states in the worst case, where n is half the total number of balls.

What Interviewers Usually Probe

Expect state transition dynamic programming recognition and careful combinatorial reasoning.
Watch for factorial handling of identical balls to avoid overcounting or undercounting.
Clarify distinction between boxes early to prevent incorrect probability assumptions.

Common Pitfalls or Variants

Common pitfalls

Confusing box identity and treating distributions as identical when boxes are distinct.
Forgetting to include all possible ways to split balls of a single color between boxes.
Ignoring memoization, leading to exponential runtime for even small input sizes.

Follow-up variants

Compute probability with more than two boxes while maintaining distinct color equality constraints.
Calculate probability when some balls are fixed in specific boxes initially, modifying DP states.
Find expected number of distinct colors in each box instead of probability equality.

FAQ

What is the key strategy for solving the Probability of Two Boxes Having The Same Number of Distinct Balls?

The key is state transition dynamic programming that tracks distributions of each color and counts of distinct balls while avoiding overcounting permutations.

Can this problem be solved using naive recursion?

Yes, but naive recursion without memoization quickly becomes infeasible due to exponential combinations, making DP essential for larger inputs.

How do I handle identical balls in DP?

Use combinatorial formulas with factorials to compute the number of ways to distribute identical balls between boxes accurately within DP states.

Does the order of boxes matter in probability calculation?

Yes, boxes are distinct, so swapping contents counts as a different distribution. Ignoring this distinction leads to incorrect probability.

What patterns should I recognize for similar problems?

Look for state transition DP patterns with multiple dimensions: current item, subset sums, and differences in counts, often paired with combinatorial counting.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        @cache
        def dfs(i: int, j: int, diff: int) -> float:
            if i >= k:
                return 1 if j == 0 and diff == 0 else 0
            if j < 0:
                return 0
            ans = 0
            for x in range(balls[i] + 1):
                y = 1 if x == balls[i] else (-1 if x == 0 else 0)
                ans += dfs(i + 1, j - x, diff + y) * comb(balls[i], x)
            return ans

        n = sum(balls) >> 1
        k = len(balls)
        return dfs(0, n, 0) / comb(n << 1, n)

Continue Practicing

#1569 number of ways to reorder array to get same bst #2597 the number of beautiful subsets #1799 maximize score after n operations