GATE Overflow Test Series | Algorithms | Test 2 | Question: 28

Question

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

Answer 1

$0-2-14-98-100$

So, total $4$ edges.

Comments

gatecse

why we haven’t taken the edge from 2-4 (as j = i +2, here j = 4, then i=2 is also 4)? even number  to even number vertex connected 0-2-4-6-8……….end so on, and odd also

---

Those edges are also there. But the question is to find the shortest path.

Answer 2

https://gateoverflow.in/3817/gate2005-it-56

Comments

Good Explanation.

Answer 3

this is similar to dynamic programming problem as every node has 2 choice either jump to 7i ^th node or i+2th node, we have to optimize number of edges but let us solve greedily  always better to back track from 100 as 98 closest 100 having edge and  divisible by 7 so before edge mus be 14 and 2 and 0 so total 4 edges