Unlock Briefcase

Moderate
0/80
Average time to solve is 30m
3 upvotes
Asked in companies
OlaPhonePePhonePe

Problem statement

There is a briefcase protected by a lock with 4 circular wheels. The password is a sequence of 4 digits.

1. Each wheel has 10 slots: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ’9’.

2. The wheels can rotate freely and wrap around, ‘9’ can be left rotated to ‘8’ and right rotated to ‘0’, similarly ‘0’ can be right rotated to ‘1’ and left rotated to ‘9’. Rotation of one wheel counts to one rotation.

3. Initially, the lock starts at “0000”, a string representing the state of four wheels.

You are given a list of dead ends (codes of 4 digits), meaning if at any point the lock displays any of these codes, the wheels of the lock will stop turning, and you will be unable to open it.

Given a target representing the code that will unlock the briefcase, return the minimum total number of turns required to open the lock, or -1 if it is not possible.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains an integer ‘N’ denoting the number of dead-end codes.

The second line of each test case contains the ‘N’ single-space separated dead-end codes.  

The third line of each test case contains a string ‘target’ representing the unlocking code.

Output Format:

For each test case, print a single line containing a single integer denoting the minimum number of rotations will be printed.

The output of each test case is printed in a separate line.

Note:

You don’t have to print anything, it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10 
1 <=  N <= 5 * 10 ^ 4
|TARGET| = 4

Where ‘T’ is the total number of test cases, ‘N’ represents the number of dead-end codes, and ‘|TARGET|’  represents the length of the target.

Time limit: 1 sec.
Sample Input 1:
1 
5
0201 0101 0102 1212 2002
0202
Sample Output 1:
6
Explanation of sample input 1:
A sequence of valid moves would be “0000” => “1000” => “1100” => “1200” => “1201” => “1202” => “0202”
Note that a sequence like “0000” => “0100” => “0200” => “0201” => “0202” would be invalid as these moves lead to a dead end “0201” after which the lock gets stuck and can’t be changed any further.
Sample Input 2:
2
1
0000 
8888
1
8888
0009
Sample Output 2:
-1
1
Hint

Breadth First Search.

Approaches (1)
Breadth First Search

The idea is to use breadth first search. Find all possible codes that can be formed after one rotation in current code and for all those codes, find the next codes that can be formed after one rotation. These steps will lead to all possible codes that can be formed from the initial string. After, say ‘r’ number of rotations, the codes formed contain a code that is equal to the given target, you have reached to the target in minimum number of rotations that is ‘r’.

 

Algorithm :  

  1. Take an unordered set, avoid,  to store all the dead end codes.
  2. Take a queue and push the initial string “0000” to it. The queue will store the next valid codes possible by increasing or decreasing a digit by one unit.
  3. If the starting code “0000” or target is present in the dead end codes, return -1.
  4. Let the current size of the queue be ‘num’. Iterate from 0 to num - 1 and do the following:
    1. Pop a code from the queue. If the code is already present in avoid, there is no need to consider this code and continue with the next iteration.
    2. If the current code is equal to the target, return the count.
    3. Insert count in avoid.
    4. Traverse all the digits in the code, once increase the digit by one unit and once decrease it keeping the remaining digits of the code constant. Push these new codes in the queue.
  5. Keep repeating step 4 until there are no further combinations left and the queue has become empty.
  6. If the queue is empty and the target is not found, return -1.
Time Complexity

O(10 ^ 4).

 

There can be 10 * 10 * 10 * 10 = 10 ^ 4  possible number of codes that can be formed from the initial string “0000”. In BFS, every code is visited at most once in the worst case. Thus, the final time complexity will be O(10 ^ 4).

Space Complexity

O(N), where N is the number of dead end codes.

 

Since we are storing all the visited codes in a map and a queue is used to store all the possible codes formed after every rotation consuming space almost equal to O(2 * (10 ^ 4)). All the dead-end codes in a map, which takes O(N). Thus, the final space complexity will be O(N + 2 * 10 ^ 4) = O(N).

Code Solution
(100% EXP penalty)
Unlock Briefcase
Full screen
Console