Last Updated: 29 Dec, 2020
Unlock Briefcase
Moderate
Asked in companies
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.
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.
Approaches
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 :
- Take an unordered set, avoid, to store all the dead end codes.
- 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.
- If the starting code “0000” or target is present in the dead end codes, return -1.
- Let the current size of the queue be ‘num’. Iterate from 0 to num - 1 and do the following:
- 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.
- If the current code is equal to the target, return the count.
- Insert count in avoid.
- 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.
- Keep repeating step 4 until there are no further combinations left and the queue has become empty.
- If the queue is empty and the target is not found, return -1.
Similar problems