# [SOLVED] Python: Find the minimum number of seconds required to make speed of vehicle equals to zero or s=0?

## Issue

#Dear all, could you help me please with this task to solve and find a code solution in Python?

#An engineer is calculating performance of a brake system for a vehicle. He wants to determine in how many seconds the brake system stops the vehicle or take the speed of the vehicle to 0. (s means SPEED of vehicle, b means BRAKE INTENSITY)

#There are 2 operations which can be performed in brake system

#Each operations take 1 sec to complete. These operations can’t happen in parallel. Your program can choose to perform any of the 2 operations at each step.

Find the minimum number of seconds required to make speed of vehicle equals to zero or s=0.

Input Format

#Each test case consists of a single line containing 2 integers. First Speed and second Brake Intensity.

``````s=>1,
b<=10**9;
``````

#Speed and Brake Intensity range –

``````s>=1,
b=<10**9;
``````

Output Format

For each test case print a single integer i.e. minimum number of seconds required to make the speed of the vehicle to 0.

Test Case 0: s = 9 and b = 2 In above test case, one of the optimal solutions is:

#Divide s by b. After this operation

``````s=4,
b=2
``````

:
#Divide s by b. After this operation

``````s=2,
b=2;
``````

#Increase b. After this operation

``````s=,
b=3;
``````

#Divide s by b. After this operation

``````s=0,
b=3;
``````

## Solution

Can be solved with recursion as follows.

Note: Simple solution but maximum recursion depth exceeded for larger values of s.

``````def min_count(s, b):
'''
Finds mininum number of operations to reduce s to 0

Each step we can either:
1. reduce s to s // b (i.e. integer division of s by b)
2.  increment b

'''
# Base cases
if s == 0:
return 0    # 0 steps, since s already 0

if b > s:
return 1    # only one step since s // b will be zero

# Recursion step
# Answer is 1 + min of both types of operationi counts
return 1 + min(min_count(s // b, b), min_count(s, b + 1))

>>> min_count(9, 2)
4
``````

Using Priority Queue

``````def solve(s, b):
'''
In each step there are two possible moves
Replace first number by the
Reduce s by s // b
increment b by 1

We use a priority queue to update the state which has made the least moves so far

'''
h = []                   # Use Priority queue so we can retrieve state with least number of moves each time
heappush(h, (0, s, b))   # Initial state: 0 moves, values s & b

while h:
# Get state which has the least number of moves
moves, s, b = heappop(h)    # Get current moves s & b

if s == 0:
return moves    # number of moves to reach 0

# Add two new states based upon two new possible moves
heappush(h, (moves + 1, s // b, b))   # increment moves by 1
heappush(h, (moves + 1, s, b + 1))    # increment moves by 1

>>> solve(9, 2)
4
>>> solve(100000000, 2)  # Recursive version can not solve this
15
``````