Last Updated: 26 Oct, 2021

Minimum Steps

Easy

Asked in companies

Solve now

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.

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.

Solve now

Approaches

01 Approach

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

Solve now

02 Approach

In this approach, we will use the same approach as before but we will create a memo 2D matrix of size NXL that will store all the answers for all pairs so N and L therefore we won’t have to recalculate them.

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)
Create an matrix of size NxL memo, initialise all the values to 1
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 memo[currentPos][curr] does not equal to -1 return memo[currentPos][curr]
- If currPos not in primeDict or curr is less than l
  - Set memo[currentPos][curr] as the minimum of util(currPos + 1, curr+ 1) and util(currPos + 2, curr + 1) + 1
  - Return memo[currentPos][curr]

Otherwise, Set memo[currentPos][curr] as theminimum of util(currPos + 1, curr+ 1), util(currPos + 2, curr + 1) and util(currPos + primeDict[currPos], 0)
Return memo[currentPos][curr]
Return util(1, l) if util(1, l) doesn’t equal to maximum int otherwise return -1

Solve now