...
Question 7822 – Theory-of-Computation
February 16, 2024
Question 1102 – Software-Engineering
February 18, 2024
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.
A
23
B
99
C
4
D
7
0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x
error: Alert: Content selection is disabled!!