Count the Number of Computer Unlocking Permutations

Count the Number of Computer Unlocking Permutations - Problem

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 computer i has complexity complexity[i].

The password for 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 rule:

You can decrypt the password for 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]).

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 10^9 + 7.

Note: The password for computer with label 0 is decrypted, not the computer with the first position in the permutation.

Input & Output

Example 1 — Basic Case

$ Input: complexity = [1,3,2]

› Output: 1

💡 Note: Only one valid permutation: [0,1,2]. Computer 0 (complexity 1) unlocks first, then computer 1 (complexity 3) can be unlocked using 0, then computer 2 (complexity 2) can be unlocked using 0.

Example 2 — Multiple Valid Sequences

$ Input: complexity = [1,2,3,4]

› Output: 1

💡 Note: Only [0,1,2,3] is valid since each computer i can only be unlocked by j where j < i and complexity[j] < complexity[i].

Example 3 — Edge Case

$ Input: complexity = [1,1]

› Output: 0

💡 Note: Computer 1 cannot be unlocked since complexity[0] = complexity[1] = 1, but we need complexity[0] < complexity[1].

Constraints

1 ≤ complexity.length ≤ 20
1 ≤ complexity[i] ≤ 10⁵

Visualization

Tap to expand

Result: 1 valid permutation

Understanding the Visualization

1

Input

Array of complexity values [1,3,2]

2

Process

Find valid unlocking sequences where j < i and complexity[j] < complexity[i]

3

Output

Count of valid permutations

Key Takeaway

🎯 Key Insight: Computer i can only be unlocked by computer j where j < i and complexity[j] < complexity[i]

Related Problems

#1 Clumsy Factorial Medium

Asked in

G Google 25 f Facebook 18 M Microsoft 15

Count the Number of Computer Unlocking Permutations — Solution

The key insight is that computer i can only be unlocked by computer j where j < i and complexity[j] < complexity[i]. Best approach uses dynamic programming with bitmasks to count valid permutations efficiently. Time: O(2^n × n²), Space: O(2^n)

Common Approaches

Approach Time Space Notes

✓ Dynamic Programming with Memoization O(2^n × n²) O(2^n) Use DP to count valid permutations without generating all of them

Brute Force - Generate All Permutations O(n! × n) O(n) Generate all possible permutations and check validity

Dynamic Programming with Memoization — Algorithm Steps

Use bitmask to represent set of unlocked computers

For each state, try unlocking each remaining valid computer

Memoize results to avoid recomputation

Return total count from all possible paths

Visualization

Tap to expand

Step-by-Step Walkthrough

1

State

Bitmask represents which computers are unlocked

2

Transition

Try unlocking each valid computer

3

Memoize

Cache results for each state

Code -

solution.c — C

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> #define MOD 1000000007 #define MAXN 20 int complexity[MAXN]; int n; int memo[1 << MAXN]; bool visited[1 << MAXN]; int dp(int mask) { if (visited[mask]) { return memo[mask]; } if (mask == (1 << n) - 1) { visited[mask] = true; memo[mask] = 1; return 1; } int count = 0; for (int i = 0; i < n; i++) { if (mask & (1 << i)) continue; bool canUnlock = false; if (i == 0) { canUnlock = true; } else { for (int j = 0; j < i; j++) { if ((mask & (1 << j)) && complexity[j] < complexity[i]) { canUnlock = true; break; } } } if (canUnlock) { count = (count + dp(mask | (1 << i))) % MOD; } } visited[mask] = true; memo[mask] = count; return count; } int solution(int* comp, int size) { n = size; for (int i = 0; i < n; i++) { complexity[i] = comp[i]; } memset(visited, false, sizeof(visited)); return dp(0); } int main() { char line[10000]; fgets(line, sizeof(line), stdin); int comp[MAXN]; int size = 0; char* token = strtok(line, "[,]"); while (token != NULL) { comp[size++] = atoi(token); token = strtok(NULL, "[,]"); } int result = solution(comp, size); printf("%d\n", result); return 0; }

Time & Space Complexity

Time Complexity

⏱️

O(2^n × n²)

2^n possible states, each state checks n computers with n validations

n

2n

⚠ Quadratic Growth

Space Complexity

O(2^n)

Memoization table stores results for each bitmask state

n

2n

⚠ Quadratic Space

8.4K Views

Medium Frequency

~35 min Avg. Time

186 Likes

Approach	Time	Space	Notes
✓ Dynamic Programming with Memoization	O(2^n × n²)	O(2^n)	Use DP to count valid permutations without generating all of them
Brute Force - Generate All Permutations	O(n! × n)	O(n)	Generate all possible permutations and check validity

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler