“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.

Dark Mode

83 votes

Best answer

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

- $ j = i+1$ (or)
- $ 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$).

0

62 votes

The conditions are given

Edge set consists of edges from i to j using either

- j = i+1 OR
- j=3i

**W****hat**** we think from here : M**inimum 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.