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 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)$.

  • 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
        }
    }
    
    

All Problems

All Solutions