Modified Ludo

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
1 upvote
Asked in companies
AmazonPark+HashedIn

Problem statement

You are given a board of‘ ‘N’ size. You can roll a dice and jump from position ‘i’ to i + 1, i + 2, i + 3, i + 4, i + 5, and i + 6 respectively. An array ‘connections’ of size ‘M’ is also provided where you can visit from the point ‘connections[i][0]’ to ‘connections[i][1]’ directly. Your task is to find the minimum number of dice rolls to reach from 1 to ‘N’ on the board.

For example: 
Consider 'N' = 10, 'connections' = [[2, 10]]

We can go from 1 -> 2 with the help of dice (the number of operations increases by 1).
We can go from 2 -> 10 as 2 is directly connected to 10. No operation is required for this.
Hence the answer is 1.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T' which denotes the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the size of the board.

The second line contains a single integer ‘M’ denoting the size of the array ‘connections’.

Each of the next ‘M’ lines contains two space-separated integers representing the elements of the array ‘connections’.
Output Format: 
For each test case, print a single integer representing the minimum number of dice rolls to reach from 1 to ‘N’ on the board.

The output of each test case will be printed in a separate line.

Note:

You do not need to input or print anything, as it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 10 ^ 6
1 <= M <= 10 ^ 6
1 <= connections[i][0], connections[i][1] <= N 

Time limit: 1 sec

Sample Input 1:

2
10
1
2 10
15
2
2 8
6 9

Sample Output 1:

1
2

Explanation of Sample Input 1:

Test case 1:
We can go from 1 -> 2 with the help of dice (the number of operations increases by 1).
We can go from 2 -> 10 as 2 is directly connected to 10. No operation is required for this.
Hence the answer is 1.

Test case 2:
We can go from 1->6 with the help of dice (the number of operations increases by 1).
We can go from 6->9 as 6 is directly connected to 9. No operation is required for this.
We can go from 9->15 with the help of dice (the number of operations increases by 1)
Hence the answer is 2.

Sample Input 2:

2
5
2
2 5 
3 5
6
1
1 6

Sample Output 2:

1
0
Hint

Try to use a depth-first search approach.

Approaches (2)
Depth First Search

We will call recursion to solve this problem.

Initially, we are at a distance 1. From here, we can either move to 

  • 1->2
  • 1->3
  • 1->4
  • 1->5
  • 1->6

Using our Dice.

If any connection of 1 is present in the array connections, then we can move from 

  • connections[i][0] -> connections[i][1]

 

So we can move in any of the above-specified directions, and then we will call recursion for the rest part. I am maintaining a dynamic array ‘dp’ to store the solution. 

 

 Algorithm:

  • Initially, we will run a loop from start to start + 6, specifying the distance we can travel from the start using dice. If we are using dice, we will add 1 to our operations.

 

  • 1->2
  • 1->3
  • 1->4
  • 1->5
  • 1->6
  • Next, we check whether we can take help of our connections,
  • connections[i][0] -> connections[i][1]
  • If we use ‘connections’ to traverse from one point to another, then we don't have to add 1 to our answer.
  • After each move, we will call recursion and store its answer in the ‘result’ variable.
  • We will store the answer to the recursive calls in a dp array.
  • The minimum of all the answers is going to be our final answer.
Time Complexity

O(N), where ‘N’ denotes the length of the board.

 

We will only be traversing the given board completely that takes O(N) time. Hence the overall time complexity is O (N).

Space Complexity

O(N), where ‘N’ denotes the length of the board.

 

The recursive stack takes the space complexity O(N) in the worst case. The memorization array also takes O(N) space. Hence the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Modified Ludo
Full screen
Console