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

This page provides solutions for the leetcode problem 1467. Probability of a Two Boxes Having The Same Number of Distinct balls.

Problem Explanation

The problem requires us to calculate the probability that two boxes will have the same number of distinct balls after shuffling $2\text{N}$ balls into two boxes, such that each box containing $\text{N}$ balls.

For example, let's say Box1 has $4$ balls of $2$ colors, red and black, and Box2 has $4$ balls of $2$ colors, black and blue. It does not matter which specific colors each box contains, but rather how many distinct colors each box contains.

Solution

For this problem, we need to consider all possible distribution possibilities. Therefore, we use the backtracking technique. More such problem can be found here.

Java

class Solution {
  double[] factorial = new double[49]; 
  
  public double getProbability(int[] balls) {
    int sum = 0;
    for(int i = 0; i < balls.length; i++) sum += balls[i];

    factorial[0] = 1;
    for(int i = 1; i < 49; i++) factorial[i] = factorial[i - 1] * i;

    double valid = backtrack(balls, 0, 0, 0, 0, 0); 
    double total = combinations(sum, sum / 2); 
    return valid / total; 
  }

  private double backtrack(int[] balls, int index, int box1Color, int box2Color,
    int box1Count, int box2Count) {
    if (index == balls.length) return box1Count == box2Count && box1Color == box2Color ? 1 : 0;
    else {
      double res = 0;
      for(int i = 0; i <= balls[index]; i++) {
        double combinations = combinations(balls[index], i);
        res += backtrack(
          balls, index + 1,
          i > 0 ? box1Color + 1 : box1Color,
          i < balls[index] ? box2Color + 1 : box2Color,
          box1Count + i,
          box2Count + (balls[index] - i)
        ) * combinations;
      }
      return res;
    }
  }

  private double combinations(int n, int r) {
    return factorial[n] / factorial[n - r] / factorial[r];
  }
}

Complexity

Let $\text{N}$ be the length of the input array $\text{balls}$

Time Complexity

Each of the $\text{N}$ indices in the input array has $2$ boxes to choose from, so total time complexity will be:

$$\text{O}(2 ^ \text{N})$$

info

Here, we ignore time complexity required to distribute elements at each of the $\text{N}$ indices into $2$ boxes, because the input constraint $1 \leq \text{balls}[\text{i}] \leq 6$ ensures that this number will be very small.

Space Complexity

Since there are $\text{N}$ indices to assign to each box, the stack size for the backtracking will be $\text{N}$, so space complexity will be:

$$\text{O}(\text{N})$$