Ninja’s Safe

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
3 upvotes
Asked in companies
UberAmazonalibaba

Problem statement

After an accident, Ninja is suffering from transient amnesia. He wants to open his safe but has forgotten his password.

The safe’s lock has 4 circular wheels. Each wheel has 10 slots: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. The wheels can rotate clockwise as well as anti-clockwise: for example, we can turn 9 to be 0, or 0 to be 9. Each move consists of turning one wheel in one slot.

The lock initially starts at 0000, a string representing the state of the 4 wheels.

Ninja is given a list of ‘blockages’ dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning, and Ninja would be unable to open it.

There would be a ‘result’ given representing the wheels' value that will unlock the lock, return the minimum total number of turns Ninja is required to open the lock, or -1 if it is impossible for him to open it.

Help Ninja to open his safe.

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

Input Format :

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains a single integer ‘N’ denoting the size of the ‘blockages’ array.

The next line contains ‘N’ space-separated strings denoting the values of the ‘blockages’ array.

The third line contains a single string denoting the ‘result’ value.

Output Format :

For each test case, print a single line containing numbers of turns or -1 as per the condition.

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

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5 
1 <= N <= 500
blockages[i].length ==  4
result.length ==  4
result will not be in the list blockages
result and blockages[i] consists of only digits from ‘0’ to ‘9’.

Time Limit: 1sec

Sample Input 1 :

2
3
2000 2020 2022
2121
5
1000 1001 1002 1010 3010
3000

Sample Output 1 :

6
5

Explanation For Sample Input 1 :

For the first test case, the initial state is 0000 and the number of moves are 0, now to reach 2121, following steps would be taken:
0000 -> 1000 [count= 1]
1000 -> 2000 [count= 2]
2000 -> 2100 [count= 3]
2100 -> 2110 [count= 4]
2110 -> 2120 [count= 5]
2120 -> 2121 [count= 6]
Hence the output is 6.

Similarly in the second test case, the initial state is 0000 and the number of moves is 0, now to achieve the result of 3000, steps would be as 0000-> 0100-> 1100-> 2100-> 3100-> 3000
The number of steps is 5, hence the output is 5.

Sample Input 2 :

1
3
0000 0001 0002
2000

Sample Output 2 :

-1

Explanation Of Sample Input 2 :

Since the initial state is 0000, there would be no option for ninja to try out the password as 0000 is present in the blockages list.
Hence the output would be -1.
Hint

Categorize the elements of blockages as visited,so that we don't encounter those in the process of achieving the result.

Approaches (2)
Iterative Approach
  • Declare a queue and a hashmap ‘visited’ and the count as ‘0’.
  • Make all the strings of ‘visited’ as true.
  • Now check whether the initial state “0000” is visited or not, if not push it into the queue.
  • Run a loop until the queue is not empty.
    • Increase the count by 1.
    • Decrease the queue size by one each time.
    • Check whether the front of the queue is the result or not; if yes, then return count-1.
    • Otherwise, check whether the top[i] is 9 or 0, if it is 9 then decrement ‘top[i]’ by 1 i.e. do top[i]--, if it is 0, then change it to 9 and sidewise check for the visited strings if they are not visited push them into the queue (here ‘top[i]’ are the digits of the string present in the front of the queue).
    • ‘count-1’ would be our final answer if opening the safe is possible.
  • Otherwise, return -1.
Time Complexity

O(1).

 

Because we know all digits will be visited after at most 10000 iterations, so time complexity is O(10000) = O(1).

Space Complexity

O(1).

 

We are using two extra data structures hashMap and queue and both of them require constant space as there can be at most 10000 elements present in each of them in the worst case.

Code Solution
(100% EXP penalty)
Ninja’s Safe
Full screen
Console