We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Cracking the Safe

Number: 754

Difficulty: Hard

Paid? No

Companies: PhonePe, Google

Problem Description

Given integers n and k, representing the length of the password and the range of digits (0 to k-1) respectively, find the shortest string such that every possible combination of n digits appears as a substring at some point in the string. This string is used to "crack the safe" since the safe checks every sequence of the last n digits entered.

Key Insights

  • The problem is equivalent to generating a de Bruijn sequence for n-length strings over an alphabet of size k.
  • Every possible n-digit combination appears exactly once as a substring in the de Bruijn sequence.
  • The idea is to view the problem through the lens of graph theory where nodes represent the (n-1) digit suffixes and edges correspond to possible n-digit combinations.
  • An Eulerian circuit (or DFS based approach) can be used to traverse every edge exactly once ensuring that all combinations are covered.

Space and Time Complexity

Time Complexity: O(k^n) – The algorithm essentially explores all possible n-length combinations. Space Complexity: O(k^n) – The space is primarily used to store visited edges and recursion stack.

Solution

We can solve this problem using a DFS approach to generate a de Bruijn sequence. The steps are:

  1. Create a starting node with (n-1) zeros.
  2. Use DFS to traverse every possible edge from the current node. An edge is represented by appending a digit to the current node.
  3. Mark each combination (edge) as visited when you traverse it.
  4. Append the digit to the result once the DFS call for that branch completes (backtracking).
  5. Finally, append the starting node to the result to complete the sequence. This method guarantees that every possible combination appears exactly once.

Code Solutions

# Python solution using DFS to generate a de Bruijn sequence
def crackSafe(n, k):
    # Initialize the set for visited combinations (edges)
    visited = set()
    result = []

    # Depth-first search helper function
    def dfs(node):
        # Try every digit in the alphabet [0, k-1]
        for digit in map(str, range(k)):
            # Form the new combination
            edge = node + digit
            # If the edge is not visited, continue DFS
            if edge not in visited:
                visited.add(edge)
                # Recursively visit the next node given by the last (n-1) characters of edge
                dfs(edge[1:])
                # Append the digit to the result (backtracking)
                result.append(digit)

    # Start with an initial node of (n-1) zeros (or empty if n=1)
    start = "0" * (n - 1)
    dfs(start)
    # The final safe sequence is the starting node appended with the result reversed
    return start + "".join(result[::-1])

# Example usage:
print(crackSafe(2, 2))
← Back to All Questions