[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

Answered By – DarrylG

Answer Checked By – Terry (BugsFixing Volunteer)