8,301 views

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

1. $4$
2. $7$
3. $23$
4. $99$

### 1 comment

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.

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$).

by

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.

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.

it has better explanation

Great solution.Thanks,  Prashant..:-)

Great explanations sir
easy to understand this solution.

Thanks
"DIVIDED & CONQUERED" algorithms at it's best😄
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.
by

Thanks a lot

1
8,860 views