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

Array Math Dynamic Programming Backtracking Combinatorics Probability and Statistics Hard

Imagine you're a statistician at a game show where contestants must predict probability outcomes! You have 2n balls of k distinct colors, and you need to calculate the probability that two boxes end up with the same number of distinct colors after a random distribution.

Given an integer array balls of size k where balls[i] represents the number of balls of color i, all balls are shuffled uniformly at random. Then, the first n balls go to Box 1 and the remaining n balls go to Box 2.

Important: The two boxes are considered different. For example, with balls of colors 'a' and 'b', the distribution [a] (b) is different from [b] (a).

Goal: Return the probability that both boxes have the same number of distinct ball colors. Your answer should be accurate within 10^-5 of the actual value.

Input & Output

example_1.py — Simple Case

$ Input: balls = [1,1]

› Output: 1.00000

💡 Note: With 1 red ball and 1 blue ball, we have only one way to distribute them: one ball per box. Both distributions ([red][blue] and [blue][red]) result in each box having exactly 1 distinct color, so probability = 1.0

example_2.py — More Complex

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

› Output: 0.66667

💡 Note: With 2 red, 1 blue, 1 green balls (4 total, 2 per box). Valid equal distributions: [RB][RG], [RG][RB], [BR][GR], [GR][BR] - each box has 2 colors. Total favorable outcomes = 8, total outcomes = 12, so probability = 8/12 = 2/3

example_3.py — Edge Case

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

› Output: 0.60000

💡 Note: With 2 red, 2 blue, 1 green, 1 yellow balls (6 total, 3 per box). After calculating all valid distributions where both boxes have equal distinct colors, the probability is 0.60000

Constraints

1 ≤ balls.length ≤ 8
1 ≤ balls[i] ≤ 6
2 * n == sum(balls) where n is the number of balls per box
Answers within 10^-5 of actual value are accepted

Visualization

Tap to expand

Asked in

G Google 12 f Meta 8 a Amazon 6 ⊞ Microsoft 4

The optimal solution uses backtracking with combinatorics to efficiently calculate probabilities. Instead of enumerating all ball arrangements, we work with color distributions and use multinomial coefficients to compute the probability of each valid distribution where both boxes have equal distinct colors.

Common Approaches

✓ Backtracking with Pruning

⏱️ Time: O(4^k) Space: O(k)

This optimal approach uses recursive backtracking to explore all valid distributions while calculating probabilities using multinomial coefficients. It avoids generating actual ball sequences and instead works with color counts directly.

Brute Force Enumeration

⏱️ Time: O(C(2n,n)) Space: O(n)

This approach generates every possible way to distribute balls between two boxes and checks which distributions result in both boxes having the same number of distinct colors. While conceptually simple, it's computationally expensive.

Backtracking with Pruning — Algorithm Steps

Use backtracking to try all valid ways to distribute each color
For each distribution, calculate its probability using multinomial coefficients
Check if both boxes have the same number of distinct colors
Sum probabilities of favorable distributions

Visualization

Tap to expand

Step-by-Step Walkthrough

Color-by-Color Distribution

Decide how many balls of each color go to each box

Pruning Invalid States

Skip distributions that can't lead to valid solutions

Multinomial Calculation

Calculate probability using combinatorial formulas

Sum Favorable Outcomes

Add up probabilities of all valid distributions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

double factorial(int n) {
    if (n <= 1) return 1.0;
    double result = 1.0;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

double multinomial(int* counts, int size) {
    int sum = 0;
    for (int i = 0; i < size; i++) sum += counts[i];
    double result = factorial(sum);
    for (int i = 0; i < size; i++) result /= factorial(counts[i]);
    return result;
}

double backtrack(int color, int* box1, int* box2, int n1, int n2,
                 int* balls, int ballsSize, int target) {
    if (color == ballsSize) {
        if (n1 != target || n2 != target) return 0.0;
        int d1 = 0, d2 = 0;
        for (int i = 0; i < ballsSize; i++) {
            if (box1[i] > 0) d1++;
            if (box2[i] > 0) d2++;
        }
        if (d1 != d2) return 0.0;
        return multinomial(box1, ballsSize) * multinomial(box2, ballsSize);
    }
    double total = 0.0;
    for (int i = 0; i <= balls[color]; i++) {
        int j = balls[color] - i;
        if (n1 + i <= target && n2 + j <= target) {
            box1[color] = i;
            box2[color] = j;
            total += backtrack(color + 1, box1, box2, n1 + i, n2 + j, balls, ballsSize, target);
        }
    }
    return total;
}

double getProbability(int* balls, int ballsSize) {
    int totalBalls = 0;
    for (int i = 0; i < ballsSize; i++) totalBalls += balls[i];
    if (totalBalls % 2 != 0) return 0.0;
    int n = totalBalls / 2;
    int* box1 = calloc(ballsSize, sizeof(int));
    int* box2 = calloc(ballsSize, sizeof(int));
    double favorable = backtrack(0, box1, box2, 0, 0, balls, ballsSize, n);
    double total = multinomial(balls, ballsSize);
    free(box1);
    free(box2);
    return favorable / total;
}

int main() {
    char input[1000];
    fgets(input, sizeof(input), stdin);

    int balls[8];
    int count = 0;

    // Parse digits from any format: "1,1" or "[1,1]" or "1 1" etc.
    char* p = input;
    while (*p && count < 8) {
        if (*p >= '0' && *p <= '9') {
            balls[count++] = strtol(p, &p, 10);
        } else {
            p++;
        }
    }

    double result = getProbability(balls, count);
    printf("%.5f\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(4^k)

For each color, we try 0 to balls[i] in first box, but pruning reduces actual complexity significantly

✓ Linear Growth

Space Complexity

O(k)

Recursive call stack depth equals number of colors

✓ Linear Space

23.4K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Backtracking with Pruning — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler