###### Question 7822 – Theory-of-Computation

February 16, 2024###### Question 1102 – Software-Engineering

February 18, 2024# Question 13909 – Data-Structures

**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 if and only if either j=i+1 or j=3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is _______.**

Correct Answer: D

**Question 658 Explanation:**

**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 the reverse way. Instead of finding a path from 1 to 100, try to find a path from 100 to 1.

So, the edge sequence with minimum number of edges is

1 → 3 → 9 → 10 → 11 → 33 → 99 → 100

which consists of 7 edges.

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 the reverse way. Instead of finding a path from 1 to 100, try to find a path from 100 to 1.

So, the edge sequence with minimum number of edges is

1 → 3 → 9 → 10 → 11 → 33 → 99 → 100

which consists of 7 edges.

23

99

4

7

Subscribe

Login

0 Comments