1,348 views
2 votes
2 votes
You are given a number lock of 4 digits and it accepts a serial input. What should be the minimum length of an input string so that the lock is guaranteed to open assuming it opens if any of the consecutive 4 digits matches the code. Also how to get one such sequence?

1 Answer

Best answer
2 votes
2 votes

Actually this problem is popular application of De Bruijn graphs.

Some idea about De Bruijn graph:

Let each node of De Bruijn graph consists of triplet $(XYZ)$. A directed arc can exists between one triplet say $(XYZ)$ to other triplet $(YZW)$ e.g there is an arc from node $(345)$ to $(459)$ since last $2$ – digits of first node is common to first $2$ – digits of second node.

Similary there is no arc from say $(245)$ to $(478)$. This way we create directed edges between nodes of De Bruijn graphs.

Properties of De Bruijn graphs:  

  1. Each De Bruijn graphs has equal no of incoming & outgoing edges which in turn equals to no of symbols used for constructing triplets(in our case we have total $10$ digits using which we can construct triplets, hence no. of incoming edges (i.e. in – degree) = no. of outgoing edges (i.e. out – degree) $= 10$.
  1. Each De Bruijn graphs is Eulerian & Hamiltonian i.e Euler cycle & Hamiltonian cycle exists. So consider Euler cycle i.e. traversing each edge only once gives us minimum sequence. So we use this property to verify that sequence we got from this graph will always minimum so our solution will be always optimised.

Now lets solve our problem:

Since we have to find key which consists of is $4$ – digit, so we first create all triplet possible of the form $<XYZ>$. So total no. of such triplets $= 10*10*10 = 1000$.

Now we will start creating directed edge between nodes following the above condition we described in $1^{st}$ properties.

So for every two triplets of the form $<XYZ>$ & $<YZW>$, we create one edge which corresponds to sequence $XYZW$. So total no. of such sequence possible $= 10*10*10*10 = 10000$.

So upto this point we have successfully constructed De Bruijn graphs.

Now our solution is simple: Take any node say $<XYZ>$ and traverse to other node say $<YZW>$ this corresponds to sequence $XYZW$ i.e., for each encounter of edge in Euler path, we add one symbol to previous node. Here we added $W$ to $XYZ$. This way we traverse through Euler Path. Now since we have total $10000$ edges and for each edges, we are adding one character, so starting from any node say $<XYZ>$, we will have finally $3+10000 =10003$ characters in sequence.

And from the property of De Bruijn graphs, this sequence will be optimal.

In short, basically this algorithm work as follows:

Let correct key is $``\ 1234"$. We start with any triplet i.e., any node in graph say $012$. After that we read one more digit sequentially say we read $`2\textrm'$ i.e., traversing through edge which will take us to $``\ 122"$. So this traversal corresponds to $``\ 0122"$. Now we compare it with correct key, since no match, so we traverse further. Now say next char we read is $``\ 3"$, so it takes us to node $``\ 223"$ i.e., we reached at node $223$ from $122$. This gives us current sequence $``1223"$ & overall sequence $``\ 01223"$. We keep on traversing the graph till we get last $4$ – character of sequence as $``\ 1234"$. So in worst case we will get a sequence of length $``\ 10003"$.

edited by

Related questions

1 votes
1 votes
1 answer
1
radha gogia asked Apr 10, 2016
2,032 views
According to me first we sort the array in O(nlogn) time and then in O(k) time , find the product , so total time complexity is O(nlogn) , so am I right or can it be done...
2 votes
2 votes
2 answers
2
Arjun asked Jul 3, 2016
2,977 views
Given an array of $n$ elements find the maximum continuous sum in it. For example consider the below array of $n=6$.23 4 -10 2 15 1Answer is 35.
1 votes
1 votes
0 answers
3
Arjun asked Jun 6, 2016
449 views
Write an object oriented code for representing boolean expressions and then a function for checking the equivalence of two boolean expressions.
0 votes
0 votes
0 answers
4
Arjun asked Jun 6, 2016
1,053 views
Given an arithmetic expression involving *, + only write an object oriented code for its representation and evaluation