Welcome to Subscribe On Youtube
3577. Count the Number of Computer Unlocking Permutations
Description
You are given an array complexity
of length n
.
There are n
locked computers in a room with labels from 0 to n - 1
, each with its own unique password. The password of the computer i
has a complexity complexity[i]
.
The password for the computer labeled 0 is already decrypted and serves as the root. All other computers must be unlocked using it or another previously unlocked computer, following this information:
- You can decrypt the password for the computer
i
using the password for computerj
, wherej
is any integer less thani
with a lower complexity. (i.e.j < i
andcomplexity[j] < complexity[i]
) - To decrypt the password for computer
i
, you must have already unlocked a computerj
such thatj < i
andcomplexity[j] < complexity[i]
.
Find the number of permutations of [0, 1, 2, ..., (n - 1)]
that represent a valid order in which the computers can be unlocked, starting from computer 0 as the only initially unlocked one.
Since the answer may be large, return it modulo 109 + 7.
Note that the password for the computer with label 0 is decrypted, and not the computer with the first position in the permutation.
Example 1:
Input: complexity = [1,2,3]
Output: 2
Explanation:
The valid permutations are:
- [0, 1, 2]
- Unlock computer 0 first with root password.
- Unlock computer 1 with password of computer 0 since
complexity[0] < complexity[1]
. - Unlock computer 2 with password of computer 1 since
complexity[1] < complexity[2]
.
- [0, 2, 1]
- Unlock computer 0 first with root password.
- Unlock computer 2 with password of computer 0 since
complexity[0] < complexity[2]
. - Unlock computer 1 with password of computer 0 since
complexity[0] < complexity[1]
.
Example 2:
Input: complexity = [3,3,3,4,4,4]
Output: 0
Explanation:
There are no possible permutations which can unlock all computers.
Constraints:
2 <= complexity.length <= 105
1 <= complexity[i] <= 109
Solutions
Solution 1: Brain Teaser
Since the password for computer number $0$ is already unlocked, for any other computer $i$, if $\text{complexity}[i] \leq \text{complexity}[0]$, it is impossible to unlock computer $i$, so we return $0$. Otherwise, any permutation is valid, and there are exactly $(n - 1)!$ possible permutations.
The time complexity is $O(n)$, where $n$ is the length of the $\text{complexity}$ array. The space complexity is $O(1)$.
-
class Solution { public int countPermutations(int[] complexity) { final int mod = (int) 1e9 + 7; long ans = 1; for (int i = 1; i < complexity.length; ++i) { if (complexity[i] <= complexity[0]) { return 0; } ans = ans * i % mod; } return (int) ans; } }
-
class Solution { public: int countPermutations(vector<int>& complexity) { const int mod = 1e9 + 7; long long ans = 1; for (int i = 1; i < complexity.size(); ++i) { if (complexity[i] <= complexity[0]) { return 0; } ans = ans * i % mod; } return ans; } };
-
class Solution: def countPermutations(self, complexity: List[int]) -> int: mod = 10**9 + 7 ans = 1 for i in range(1, len(complexity)): if complexity[i] <= complexity[0]: return 0 ans = ans * i % mod return ans
-
func countPermutations(complexity []int) int { mod := int64(1e9 + 7) ans := int64(1) for i := 1; i < len(complexity); i++ { if complexity[i] <= complexity[0] { return 0 } ans = ans * int64(i) % mod } return int(ans) }
-
function countPermutations(complexity: number[]): number { const mod = 1e9 + 7; let ans = 1; for (let i = 1; i < complexity.length; i++) { if (complexity[i] <= complexity[0]) { return 0; } ans = (ans * i) % mod; } return ans; }
-
impl Solution { pub fn count_permutations(complexity: Vec<i32>) -> i32 { const MOD: i64 = 1_000_000_007; let mut ans = 1i64; for i in 1..complexity.len() { if complexity[i] <= complexity[0] { return 0; } ans = ans * i as i64 % MOD; } ans as i32 } }