Probability of a Two Boxes Having The Same Number of Distinct Balls
<p>Given <code>2n</code> balls of <code>k</code> distinct colors. You will be given an integer array <code>balls</code> of size <code>k</code> where <code>balls[i]</code> is the number of balls of color <code>i</code>.</p>

<p>All the balls will be <strong>shuffled uniformly at random</strong>, then we will distribute the first <code>n</code> balls to the first box and the remaining <code>n</code> balls to the other box (Please read the explanation of the second example carefully).</p>

<p>Please note that the two boxes are considered different. For example, if we have two balls of colors <code>a</code> and <code>b</code>, and two boxes <code>[]</code> and <code>()</code>, then the distribution <code>[a] (b)</code> is considered different than the distribution <code>[b] (a) </code>(Please read the explanation of the first example carefully).</p>

<p>Return<em> the probability</em> that the two boxes have the same number of distinct balls. Answers within <code>10<sup>-5</sup></code> of the actual value will be accepted as correct.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> balls = [1,1]
<strong>Output:</strong> 1.00000
<strong>Explanation:</strong> 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
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> balls = [2,1,1]
<strong>Output:</strong> 0.66667
<strong>Explanation:</strong> 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
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> balls = [1,2,1,2]
<strong>Output:</strong> 0.60000
<strong>Explanation:</strong> 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
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= balls.length &lt;= 8</code></li>
	<li><code>1 &lt;= balls[i] &lt;= 6</code></li>
	<li><code>sum(balls)</code> is even.</li>
</ul>

[]
[]
[{"value": "cpp", "text": "C++", "defaultCode": "class Solution {\npublic:\n    double getProbability(vector<int>& balls) {\n        \n    }\n};"}, {"value": "java", "text": "Java", "defaultCode": "class Solution {\n    public double getProbability(int[] balls) {\n        \n    }\n}"}, {"value": "python", "text": "Python", "defaultCode": "class Solution(object):\n    def getProbability(self, balls):\n        \"\"\"\n        :type balls: List[int]\n        :rtype: float\n        \"\"\"\n        "}, {"value": "python3", "text": "Python3", "defaultCode": "class Solution:\n    def getProbability(self, balls: List[int]) -> float:\n        "}, {"value": "c", "text": "C", "defaultCode": "double getProbability(int* balls, int ballsSize) {\n    \n}"}, {"value": "csharp", "text": "C#", "defaultCode": "public class Solution {\n    public double GetProbability(int[] balls) {\n        \n    }\n}"}, {"value": "javascript", "text": "JavaScript", "defaultCode": "/**\n * @param {number[]} balls\n * @return {number}\n */\nvar getProbability = function(balls) {\n    \n};"}, {"value": "typescript", "text": "TypeScript", "defaultCode": "function getProbability(balls: number[]): number {\n    \n};"}, {"value": "php", "text": "PHP", "defaultCode": "class Solution {\n\n    /**\n     * @param Integer[] $balls\n     * @return Float\n     */\n    function getProbability($balls) {\n        \n    }\n}"}, {"value": "swift", "text": "Swift", "defaultCode": "class Solution {\n    func getProbability(_ balls: [Int]) -> Double {\n        \n    }\n}"}, {"value": "kotlin", "text": "Kotlin", "defaultCode": "class Solution {\n    fun getProbability(balls: IntArray): Double {\n        \n    }\n}"}, {"value": "dart", "text": "Dart", "defaultCode": "class Solution {\n  double getProbability(List<int> balls) {\n    \n  }\n}"}, {"value": "golang", "text": "Go", "defaultCode": "func getProbability(balls []int) float64 {\n    \n}"}, {"value": "ruby", "text": "Ruby", "defaultCode": "# @param {Integer[]} balls\n# @return {Float}\ndef get_probability(balls)\n    \nend"}, {"value": "scala", "text": "Scala", "defaultCode": "object Solution {\n    def getProbability(balls: Array[Int]): Double = {\n        \n    }\n}"}, {"value": "rust", "text": "Rust", "defaultCode": "impl Solution {\n    pub fn get_probability(balls: Vec<i32>) -> f64 {\n        \n    }\n}"}, {"value": "racket", "text": "Racket", "defaultCode": "(define/contract (get-probability balls)\n  (-> (listof exact-integer?) flonum?)\n  )"}, {"value": "erlang", "text": "Erlang", "defaultCode": "-spec get_probability(Balls :: [integer()]) -> float().\nget_probability(Balls) ->\n  ."}, {"value": "elixir", "text": "Elixir", "defaultCode": "defmodule Solution do\n  @spec get_probability(balls :: [integer]) :: float\n  def get_probability(balls) do\n    \n  end\nend"}]
{
  "name": "getProbability",
  "params": [
    {
      "name": "balls",
      "type": "integer[]"
    }
  ],
  "return": {
    "type": "double"
  }
}
{"cpp": ["C++", "<p>Compiled with <code> clang 19 </code> using the latest C++ 23 standard, and <code>libstdc++</code> provided by GCC 14.</p>\r\n\r\n<p>Your code is compiled with level two optimization (<code>-O2</code>). <a href=\"https://github.com/google/sanitizers/wiki/AddressSanitizer\" target=\"_blank\">AddressSanitizer</a> is also enabled to help detect out-of-bounds and use-after-free bugs.</p>\r\n\r\n<p>Most standard library headers are already included automatically for your convenience.</p>"], "java": ["Java", "<p><code>OpenJDK 21</code>. Using compile arguments: <code>--enable-preview --release 21</code></p>\r\n\r\n<p>Most standard library headers are already included automatically for your convenience.</p>\r\n<p>Includes <code>Pair</code> class from https://docs.oracle.com/javase/8/javafx/api/javafx/util/Pair.html.</p>"], "python": ["Python", "<p><code>Python 2.7.18</code>.</p>\r\n\r\n<p>Most libraries are already imported automatically for your convenience, such as <a href=\"https://docs.python.org/2/library/array.html\" target=\"_blank\">array</a>, <a href=\"https://docs.python.org/2/library/bisect.html\" target=\"_blank\">bisect</a>, <a href=\"https://docs.python.org/2/library/collections.html\" target=\"_blank\">collections</a>. If you need more libraries, you can import it yourself.</p>\r\n\r\n<p>For Map/TreeMap data structure, you may use <a href=\"http://www.grantjenks.com/docs/sortedcontainers/\" target=\"_blank\">sortedcontainers</a> library.</p>\r\n\r\n<p>Note that Python 2.7 <a href=\"https://www.python.org/dev/peps/pep-0373/\" target=\"_blank\">is not maintained anymore</a>. For the latest Python, please choose Python3 instead.</p>"], "c": ["C", "<p>Compiled with <code>gcc 14</code> using the gnu11 standard.</p>\r\n\r\n<p>Your code is compiled with level one optimization (<code>-O2</code>). <a href=\"https://github.com/google/sanitizers/wiki/AddressSanitizer\" target=\"_blank\">AddressSanitizer</a> is also enabled to help detect out-of-bounds and use-after-free bugs.</p>\r\n\r\n<p>Most standard library headers are already included automatically for your convenience.</p>\r\n\r\n<p>For hash table operations, you may use <a href=\"https://troydhanson.github.io/uthash/\" target=\"_blank\">uthash</a>. \"uthash.h\" is included by default. Below are some examples:</p>\r\n\r\n<p><b>1. Adding an item to a hash.</b>\r\n<pre>\r\nstruct hash_entry {\r\n    int id;            /* we'll use this field as the key */\r\n    char name[10];\r\n    UT_hash_handle hh; /* makes this structure hashable */\r\n};\r\n\r\nstruct hash_entry *users = NULL;\r\n\r\nvoid add_user(struct hash_entry *s) {\r\n    HASH_ADD_INT(users, id, s);\r\n}\r\n</pre>\r\n</p>\r\n\r\n<p><b>2. Looking up an item in a hash:</b>\r\n<pre>\r\nstruct hash_entry *find_user(int user_id) {\r\n    struct hash_entry *s;\r\n    HASH_FIND_INT(users, &user_id, s);\r\n    return s;\r\n}\r\n</pre>\r\n</p>\r\n\r\n<p><b>3. Deleting an item in a hash:</b>\r\n<pre>\r\nvoid delete_user(struct hash_entry *user) {\r\n    HASH_DEL(users, user);  \r\n}\r\n</pre>\r\n</p>"], "csharp": ["C#", "<p><a href=\"https://learn.microsoft.com/en-us/dotnet/csharp/whats-new/csharp-13\" target=\"_blank\">C# 13</a> with .NET 9 runtime</p>"], "javascript": ["JavaScript", "<p><code>Node.js 22.14.0</code>.</p>\r\n\r\n<p>Your code is run with <code>--harmony</code> flag, enabling <a href=\"http://node.green/\" target=\"_blank\">new ES6 features</a>.</p>\r\n\r\n<p><a href=\"https://lodash.com\" target=\"_blank\">lodash.js</a> library is included by default.</p>\r\n\r\n<p>For Priority Queue / Queue data structures, you may use 6.3.2 version of <a href=\"https://github.com/datastructures-js/priority-queue/tree/v6.3.2\" target=\"_blank\">datastructures-js/priority-queue</a> and 4.2.3 version of <a href=\"https://github.com/datastructures-js/queue/tree/v4.2.3\" target=\"_blank\">datastructures-js/queue</a> and 1.0.4 version of <a href=\"https://github.com/datastructures-js/deque/tree/v1.0.4\" target=\"_blank\">datastructures-js/deque</a>.</p>"], "ruby": ["Ruby", "<p><code>Ruby 3.2</code></p>\r\n\r\n<p>Some common data structure implementations are provided in the Algorithms module: https://www.rubydoc.info/github/kanwei/algorithms/Algorithms</p>"], "swift": ["Swift", "<p><code>Swift 6.0</code>.</p>\r\n\r\n<p>You may use the following packages:<br/>\r\n<a href=\"https://github.com/apple/swift-algorithms/tree/1.2.0\" target=\"_blank\">swift-algorithms 1.2.0</a><br/>\r\n<a href=\"https://github.com/apple/swift-collections/tree/1.1.4\" target=\"_blank\">swift-collections 1.1.4</a><br/>\r\n<a href=\"https://github.com/apple/swift-numerics/tree/1.0.2\" target=\"_blank\">swift-numerics 1.0.2</a></p>"], "golang": ["Go", "<p><code>Go 1.23</code></p>\r\n<p>Support <a href=\"https://pkg.go.dev/github.com/emirpasic/gods@v1.18.1\" target=\"_blank\">https://pkg.go.dev/github.com/emirpasic/gods@v1.18.1</a> and <a href=\"https://pkg.go.dev/github.com/emirpasic/gods/v2@v2.0.0-alpha\" target=\"_blank\">https://pkg.go.dev/github.com/emirpasic/gods/v2@v2.0.0-alpha</a> library.</p>"], "python3": ["Python3", "<p><code>Python 3.11</code>.</p>\r\n\r\n<p>Most libraries are already imported automatically for your convenience, such as <a href=\"https://docs.python.org/3/library/array.html\" target=\"_blank\">array</a>, <a href=\"https://docs.python.org/3/library/bisect.html\" target=\"_blank\">bisect</a>, <a href=\"https://docs.python.org/3/library/collections.html\" target=\"_blank\">collections</a>. If you need more libraries, you can import it yourself.</p>\r\n\r\n<p>For Map/TreeMap data structure, you may use <a href=\"http://www.grantjenks.com/docs/sortedcontainers/\" target=\"_blank\">sortedcontainers</a> library.</p>"], "scala": ["Scala", "<p><code>Scala 3.3.1</code>.</p>"], "kotlin": ["Kotlin", "<p><code>Kotlin 2.1.10</code>.</p>"], "rust": ["Rust", "<p><code>Rust 1.85.0</code>. Your code will be compiled with <code>opt-level</code> 2.</p>\r\n\r\n<p>Supports <a href=\"https://crates.io/crates/rand\" target=\"_blank\">rand v0.8</a> and <a href=\"https://crates.io/crates/regex\" target=\"_blank\">regex\u00a0v1</a> and <a href=\"https://crates.io/crates/itertools\" target=\"_blank\">itertools\u00a0v0.14</a> from crates.io</p>"], "php": ["PHP", "<p><code>PHP 8.2</code>.</p>\r\n<p>With bcmath module</p>"], "typescript": ["Typescript", "<p><code>TypeScript 5.7.3, Node.js 22.14.0</code>.</p>\r\n\r\n<p>Compile Options: <code>--alwaysStrict --strictBindCallApply --strictFunctionTypes --target ES2024</code></p>\r\n\r\n<p><a href=\"https://lodash.com\" target=\"_blank\">lodash.js</a> library is included by default.</p>\r\n\r\n<p>For Priority Queue / Queue data structures, you may use 6.3.2 version of <a href=\"https://github.com/datastructures-js/priority-queue/tree/v6.3.2\" target=\"_blank\">datastructures-js/priority-queue</a> and 4.2.3 version of <a href=\"https://github.com/datastructures-js/queue/tree/v4.2.3\" target=\"_blank\">datastructures-js/queue</a> and 1.0.4 version of <a href=\"https://github.com/datastructures-js/deque/tree/v1.0.4\" target=\"_blank\">datastructures-js/deque</a>.</p>"], "racket": ["Racket", "<p><a href=\"https://docs.racket-lang.org/guide/performance.html#%28tech._c%29\" target=\"_blank\">Racket CS</a> v8.15</p>\r\n\r\n<p>Using <code>#lang racket</code></p>\r\n\r\n<p>Required <code>data/gvector data/queue data/order data/heap</code> automatically for your convenience</p>"], "erlang": ["Erlang", "Erlang/OTP 26"], "elixir": ["Elixir", "Elixir 1.17 with Erlang/OTP 26"], "dart": ["Dart", "<p>Dart 3.2. You may use package <a href=\"https://pub.dev/packages/collection/versions/1.18.0\" target=\"_blank\">collection</a></p>\r\n\r\n<p>Your code will be run directly without compiling</p>"]}
['Array', 'Math', 'Dynamic Programming', 'Backtracking', 'Combinatorics', 'Probability and Statistics']