GATE IT 2005 | Question: 56

Question

Let $G$ be a directed graph whose vertex set is the set of numbers from $1$ to $100$. There is an edge from a vertex $i$ to a vertex $j$ iff either $j = i + 1$ or $j = 3i$. The minimum number of edges in a path in $G$ from vertex $1$ to vertex $100$ is

• A. $4$
• B. $7$
• C. $23$
• D. $99$

Comments

If anyone approaches the question thinking

“There is another path also which gives the same answer.

1-->3-->4-->12-->11-->33-->99-->100  (so 7 edges required)”

then this approach is wrong. since there is path from (11 to 12) but not (12 to 11) directed graph is given.

Answer 1

Edge set consists of edges from $i$ to $j$ using either 

1. $ j = i+1$ (or)
2. $ j=3i.$

Second option will help us reach from $1$ to $100$ rapidly. The trick to solve this question is to think in reverse way. Instead of finding a path from $1$ to $100$, try to find a path from $100$ to $1$.

The edge sequence with minimum number of edges is $1\rightarrow3\rightarrow9\rightarrow10\rightarrow11\rightarrow33\rightarrow99 - 100$ which consists of $7$ edges. 
The answer is option ($B$).

Comments

ans y not a) thts 4 beacuse 1-3-9-27-51

by condition j=3i..

kindly explain

---

finally u r at  51 not at 100.. do j = i+1 until u reach 100..

---

sir , i was solving in this without see answer

p(A∪B)=P(A)+P(B)-P(A∩B)

P(A) i assume here: j=i+1 with this i get ..99 edges

P(B) i assume J=3i with this i got  4 edges

P(A∩B)=got 80 edges.

therfore ans is 23. finally wt i see my ans was wrong.! why ans is not 23.????

---

union of two set is not minimum one,thats why..In qs minimum was asked..if minimum keyword was not given..Then 23 should be answer.

Answer 2

The conditions are given
Edge set consists of edges from i to j using either

1.  j = i+1 OR
2.  j=3i

What we think from here :  Minimum we take vertex 1 max we take vertex 100

Now one important point is to reach 100 the maximum number  which gets   j = 3*i where i= 33 so j = 3*33 = 99

Half problem is solved.
We got                                                                   1--33--99--100
Now see to reach 33 how many minimum edges needed.
Maximum number between which get value j= 3i, i= 11 so j= 3*11= 33

What we get                                                               1--11--33--99--100
So, problem solved almost minimum edge need to reach 11 from 1

Max number i which get j= 3i, i= 3 so j= 3*i =9 to reach 11 ..9--10--11
So we got another point
                                                                                  1--9--10--11--33--99--100

Now to reach 11 from 1
Max value of i = 3 so j= 3*i= 9 so 3--9
                                                                                 1--3--9--10--11--33--99--100

Note: Solved problem into half give u an idea how to get minimum for rest of the graph.

Comments

Great explanations sir

---

easy to understand this solution.

Thanks

---

"DIVIDED & CONQUERED" algorithms at it's best😄

Answer 3

The desired path (from end to begin) will be 100--99--33--11--10--9--3—1

The edges between them is as per the condition mentioned in the question. Hence min. path length is 7.

Comments

Thanks a lot

---

yeah right!!