Press "Enter" to skip to content

Posts tagged as “permutation”

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

Given 2n balls of k distinct colors. You will be given an integer array balls of size k where balls[i] is the number of balls of color i

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

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

We want to calculate the probability that the two boxes have the same number of distinct balls.

Example 1:

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

Example 4:

Input: balls = [3,2,1]
Output: 0.30000
Explanation: The set of balls is [1, 1, 1, 2, 2, 3]. It is hard to display all the 60 possible random shuffles of this set but it is easy to check that 18 of them will have the same number of distinct colors in each box.
Probability = 18 / 60 = 0.3

Example 5:

Input: balls = [6,6,6,6,6,6]
Output: 0.90327

Constraints:

  • 1 <= balls.length <= 8
  • 1 <= balls[i] <= 6
  • sum(balls) is even.
  • Answers within 10^-5 of the actual value will be accepted as correct.

Solution 0: Permutation (TLE)

Enumerate all permutations of the balls, count valid ones and divide that by the total.

Time complexity: O((8*6)!) = O(48!)
After deduplication: O(48!/(6!)^8) ~ 1.7e38
Space complexity: O(8*6)

C++

Solution 1: Combination

For each color, put n_i balls into box1, the left t_i – n_i balls go to box2.
permutations = fact(n//2) / PROD(fact(n_i)) * fact(n//2) * PROD(fact(t_i – n_i))
E.g
balls = [1×2, 2×6, 3×4]
One possible combination:
box1: 1 22 333
box2: 1 2222 3
permutations = 6! / (1! * 2! * 3!) * 6! / (1! * 4! * 1!) = 1800

Time complexity: O((t+1)^k) = O(7^8)
Space complexity: O(k + (t*k)) = O(8 + 48)

C++

vector version

C++

花花酱 LeetCode 1359. Count All Valid Pickup and Delivery Options

Given n orders, each order consist in pickup and delivery services. 

Count all valid pickup/delivery possible sequences such that delivery(i) is always after of pickup(i). 

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: n = 1
Output: 1
Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.

Example 2:

Input: n = 2
Output: 6
Explanation: All possible orders: 
(P1,P2,D1,D2), (P1,P2,D2,D1), (P1,D1,P2,D2), (P2,P1,D1,D2), (P2,P1,D2,D1) and (P2,D2,P1,D1).
This is an invalid order (P1,D2,P2,D1) because Pickup 2 is after of Delivery 2.

Example 3:

Input: n = 3
Output: 90

Constraints:

  • 1 <= n <= 500

Solution: Combination

Let dp[i] denote the number of valid sequence of i nodes.

For i-1 nodes, the sequence length is 2(i-1).
For the i-th nodes,
If we put Pi at index = 0, then we can put Di at 1, 2, …, 2i – 2 => 2i-1 options.
If we put Pi at index = 1, then we can put Di at 2,3,…, 2i – 2 => 2i – 2 options.

If we put Pi at index = 2i-1, then we can put Di at 2i – 1=> 1 option.
There are total (2i – 1 + 1) / 2 * (2i – 1) = i * (2*i – 1) options

dp[i] = dp[i – 1] * i * (2*i – 1)

or

dp[i] = 2n! / 2^n

C++

花花酱 LeetCode 46. Permutations

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Solution: DFS

Time complexity: O(n!)
Space complexity: O(n)

C++

Related Problems

花花酱 LeetCode 60. Permutation Sequence

The set [1,2,3,...,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given n and k, return the kth permutation sequence.

Note:

  • Given n will be between 1 and 9 inclusive.
  • Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

Solution: Math

Time complexity: O(n)
Space complexity: O(n)

C++

花花酱 LeetCode 1175. Prime Arrangements

Return the number of permutations of 1 to n so that prime numbers are at prime indices (1-indexed.)

(Recall that an integer is prime if and only if it is greater than 1, and cannot be written as a product of two positive integers both smaller than it.)

Since the answer may be large, return the answer modulo 10^9 + 7.

Example 1:

Input: n = 5
Output: 12
Explanation: For example [1,2,5,4,3] is a valid permutation, but [5,2,3,4,1] is not because the prime number 5 is at index 1.

Example 2:

Input: n = 100
Output: 682289015

Constraints:

  • 1 <= n <= 100

Solution: Permutation

Count the number of primes in range [1, n], assuming there are p primes and n – p non-primes, we can permute each group separately.
ans = p! * (n – p)!

Time complexity: O(nsqrt(n))
Space complexity: O(1)

C++