I am given an array, arr=[3,4,2,3,0,3,1,2,1], and a startIndex. When I am at an index i, I can move left or right by arr[i]. My task is to find if I can reach 0. Can anyone help me with the approach? Thank you :)
Asked
Active
Viewed 120 times
0
-
Your answer is already in the tags you used: use a graph search algorithm. Depth-first or breadth-first would do. – user2357112 Jul 08 '17 at 05:12
-
If you're encountering some specific issue in your attempts to apply such algorithms, please ask about your specific issue. – user2357112 Jul 08 '17 at 05:13
-
I just took a hint that I have to use dfs or bfs, but I am not able to get the whole approach, like how do I start – Pritom Mazumdar Jul 08 '17 at 05:20
1 Answers
0
The solution is path-finding in a graph
The real problem here is not getting a solution, it's modeling the problem correctly. The solution is trivial.
First off, you don't really have an array. What you have is a graph. If you have never done any graph theory, this will be a bit complicated.
Each index in your array is a node. The value stored at that index gives you the lines linking it to the other nodes with arrows indicating the direction of movement. For example, the array you specified gives you the following graph:
Each node is marked with it's position in the array (0 through 8). The node you want to reach is in red. This is supposing you can move forward to the beginning of the array once you reach the end of the array and vice-versa.
All you have to do now is find a path between 4 and your startIndex. You can apply Dijkstra's algorithm to find the shortest path.
Great. Now how do I make a graph?
If you don't have any idea on how to implement a graph, you can check this stackoverflow question for a java implementation.
You can easily find implementations for any other language.
Queder
- 310
- 3
- 11