Skip to content

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 computer j, where j is any integer less than i with a lower complexity. (i.e. j < i and complexity[j] < complexity[i])
  • To decrypt the password for computer i, you must have already unlocked a computer j such that j < i and complexity[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)\).

1
2
3
4
5
6
7
8
9
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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
    }
}

Comments