Minimum Steps

Easy
0/40
profile
Contributed by
7 upvotes
Asked in companies
ShareChatIntuitReliance Jio

Problem statement

You are given an integer ‘N,’ and your task is to find the minimum steps to reach from 1 to 'N'. There are also ‘M’ mines on which you can not move.

In each step, you can move in the following way:

1 - You move either 1 or 2 steps forward.

2 - Whenever you are at a prime number, you can make a special move, where you can move to the sum of digits in (Count the number of primes before the current prime + Difference between the next prime and current number) until it becomes a single-digit number. 

3- If you make a special move, you can’t make another special move for the next ‘L’ moves.
For Example: 
You are given ‘N’ = 10, L = 2, and mines = [6], Here you can make the following moves for minimum path 1 -> 3 -> 5 (special move) -> 9 -> 10. Hence the answer is 4.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains three space-separated integers ‘N’, ‘L’ and ‘M’, representing the position to reach, the given integer, and the number of mines, respectively.

The next lines contain ‘M’ space-separated integers representing the position of each mine.
Output Format: 
For each test case, print a single integer denoting the minimum number of steps required to reach ‘N.’

Print a separate line for each test case.
Constraints: 
1 <= T <= 10
1 <= M < N <= 10^5
0 <= L <= 10

It is guaranteed that the sum of 'N' and the sum of 'M' over all test cases doesn't exceed 10^5.
Time Limit: 1 sec.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the function.
Sample Input 1:
2
10 2 1
6
14 2 1
8
Sample Output 1:
4
4
Explanation:
For the first test case, ‘N’ = 10, L = 2, and mines = [6], Here you can make the following moves for minimum path 1 -> 3 - >5(special move) -> 9->10. Hence the answer is 4.

For the second test case, 'N' = 11, L = 2 and mines = [8], Here you can make the following moves for 1 -> 3-> 6 -> 7(special move) -> 11.
Sample Input 2:
2
12 1 1
10
6 1 1
4
Sample Output 2:
5
2
Hint

 Try to use recursion to find all the possible paths.

Approaches (2)
Recursion

In this approach, we will visit all the possible places we can visit from the current position. If any of the position is not possible, we will return maximum int.

We can go to one or two places ahead unless it’s a prime number, then check for a special move from any number we are currently on.

 

We create two utility functions: getPrimes (n), which returns an array of prime numbers for 2 to n, and the other function, digitalSum(n), returns the sum of digits until it’s a single-digit number.

 

We will also create a utility function util(currentPos, curr), where currentPos is the current position of the number and curr is the normal moves left before a special move is allowed.

 

Algorithm:

  • In the function getPrimes(n)
    • Create an empty array primes of size n + 1
    • Set primes[0] and primes[1] as False
    • Iterate i from 2 to square root of n
      • If primes[i] is false, continue the loop
      • Iterate j from i*i to n, with the increment of i
        • Set primes[j] as false
    • Return array of all indices in primes array where primes[index] is true
  • In the function digitalSum(n)
    • If n is 0 return n
    • If n is divisible by 9 return 9
    • Otherwise return n % 9
  • Insert all elements of the mines into the set mineSet
  • Create an empty hashmaps primeDict
  • Set primeNumbers as getPrimes(100010)
  • Iterate i through all but last index for primeNumbers
    • Set num as i + primeNumbers[i - 1] - primeNumbers[i]
    • Set primeDict[primeNumbers[i - 1]] as digitalSum(num)
  • In the lamda function util(currPos, curr)
    • If currPos is equal to n return 0
    • If currPos is greater than n or currPos is in mineSet return maximum int
    • Set curr as the minimum of curr and l
    • If currPos not in primeDict or curr is less than l
      • Return minimum of util(currPos + 1, curr+ 1) and util(currPos + 2, curr + 1) + 1
    • Other return minimum of util(currPos + 1, curr+ 1), util(currPos + 2, curr + 1) and util(currPos + primeDict[currPos], 0)
  • Return util(1, l) if util(1, l) doesn’t equal to maximum int otherwise return -1
Time Complexity

O(2^N), Where N is the final position to be reached.
 

There are two or three different recursive calls for each step, which will cost on average O(2^N) time. Hence the final time complexity is O(2^N).

Space Complexity

O(N), Where N is the final position to be reached.

 

The total space complexity of the recursive stack, primes array, and map is O(N) in the worst case. Hence the overall space complexity is O(N)

Code Solution
(100% EXP penalty)
Minimum Steps
Full screen
Console