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

46 votes

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

- $4$
- $7$
- $23$
- $99$

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

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