{x}
blog image

Cracking the Safe

There is a safe protected by a password. The password is a sequence of n digits where each digit can be in the range [0, k - 1].

The safe has a peculiar way of checking the password. When you enter in a sequence, it checks the most recent n digits that were entered each time you type a digit.

  • For example, the correct password is "345" and you enter in "012345":
    • After typing 0, the most recent 3 digits is "0", which is incorrect.
    • After typing 1, the most recent 3 digits is "01", which is incorrect.
    • After typing 2, the most recent 3 digits is "012", which is incorrect.
    • After typing 3, the most recent 3 digits is "123", which is incorrect.
    • After typing 4, the most recent 3 digits is "234", which is incorrect.
    • After typing 5, the most recent 3 digits is "345", which is correct and the safe unlocks.

Return any string of minimum length that will unlock the safe at some point of entering it.

 

Example 1:

Input: n = 1, k = 2
Output: "10"
Explanation: The password is a single digit, so enter each digit. "01" would also unlock the safe.

Example 2:

Input: n = 2, k = 2
Output: "01100"
Explanation: For each possible password:
- "00" is typed in starting from the 4th digit.
- "01" is typed in starting from the 1st digit.
- "10" is typed in starting from the 3rd digit.
- "11" is typed in starting from the 2nd digit.
Thus "01100" will unlock the safe. "10011", and "11001" would also unlock the safe.

 

Constraints:

  • 1 <= n <= 4
  • 1 <= k <= 10
  • 1 <= kn <= 4096

Solution Explanation: Cracking the Safe

This problem can be elegantly solved using the concept of an Eulerian circuit in graph theory. Let's break down the solution:

1. Graph Representation:

The problem can be modeled as a directed graph where:

  • Nodes: Each node represents a unique sequence of n-1 digits. For example, if n=3 and k=2, the nodes would be "00", "01", "10", "11".

  • Edges: A directed edge exists from node u to node v if appending a digit x (0 ≤ x < k) to u results in a sequence where the last n-1 digits form v. The edge is labeled with the digit x.

2. Eulerian Circuit:

An Eulerian circuit is a path in a graph that visits every edge exactly once and ends at the starting node. Our constructed graph has the property that:

  • Every node has an in-degree equal to its out-degree (each node has k incoming and k outgoing edges). This is a necessary and sufficient condition for the existence of an Eulerian circuit in a directed graph.

3. Algorithm:

The algorithm uses Depth-First Search (DFS) to find an Eulerian circuit:

  1. Initialization: Start at the node "0" (repeated n-1 times).
  2. DFS Traversal: Recursively explore the graph. For each node:
    • Iterate through all possible digits (0 to k-1).
    • If adding a digit x leads to a new, unvisited edge, add the edge to the path (visit it), update the current node, and recursively call DFS from the new node.
  3. Path Construction: The path is built by appending digits as we traverse the graph during DFS. The order of digits accumulated during DFS gives the sequence of the path.
  4. Completion: Once all edges have been visited (DFS completes), append the initial n-1 zeros to the end to ensure the final sequence unlocks the safe.

Time Complexity: O(kn)

The graph has k(n-1) nodes and k * k(n-1) = kn edges. The DFS traversal visits each edge exactly once.

Space Complexity: O(kn)

The space complexity is dominated by the vis set (to track visited edges) which can store up to kn elements in the worst case. The recursion stack during DFS can also have depth up to kn.

Code Examples (Python):

class Solution:
    def crackSafe(self, n: int, k: int) -> str:
        mod = 10**(n-1)
        visited = set()
        ans = []
 
        def dfs(u):
            for i in range(k):
                v = (u * 10 + i) % mod
                if (u, i) not in visited:
                    visited.add((u, i))
                    dfs(v)
                    ans.append(str(i))
 
        dfs(0)
        ans.extend(['0'] * (n - 1))  # Add trailing zeros
        return ''.join(ans)

Other languages (Java, C++, Go, Typescript) follow a similar structure, with minor variations in syntax and data structures used for the graph representation and visited edges tracking. The core algorithm remains the same — DFS-based Eulerian circuit construction.