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


#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.


#Speed and Brake Intensity range –


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


#Divide s by b. After this operation


#Increase b. After this operation


#Divide s by b. After this operation



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)

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)
>>> solve(100000000, 2)  # Recursive version can not solve this

Answered By – DarrylG

Answer Checked By – Terry (BugsFixing Volunteer)

Leave a Reply

Your email address will not be published. Required fields are marked *