Accenture OA-21 2024

Problem Description

You are in charge of a convoy of N vehicles, each with a fuel meter showing the fuel present in each vehicle in liters. Each vehicle needs to travel a distance of X kilometers. If the fuel becomes empty before reaching X kilometers, the vehicle can refuel but the refueling will be of X liters. If the vehicle completes the X kilometers where fuel is left over, then the extra fuel will be given to the next vehicle in the convoy. You must rearrange the convoy such that the vehicles take minimum refueling stops.

Your task is to find and return an integer value representing the minimum number of refueling stops required by the convoy of vehicles.

Note:

• The vehicles can go 1 kilometre in a single litre.
• The refuelling at any point in time will be for X litres only.

Input Format:

• input1: An integer value X, representing the distance to be travelled.
• input2: An integer value N, representing the number of vehicles in the convoy.
• input3: An integer array A of size N, representing the initial fuel in each vehicle.

Output Format:

Return an integer value representing the minimum number of refuelling stops required by the convoy of vehicles.

Constraints:

• 1 < X < 10^6: The distance to be travelled in kilometres.
• 1 <= N <= 1000: The number of vehicles in the convoy.
• 0<= Ali] <= 10^6: The initial fuel in each vehicle.

Example

Sample Input:

X = 10
N = 3
A = [3, 8, 5]

Sample Output:

1

Explanation:
Rearrange the convoy as [8, 5, 3].

• The first vehicle can travel 10 kilometers without refueling.
• The second vehicle can travel 10 kilometers without refueling.
• The third vehicle can travel only 5 kilometers.
• The first two vehicles give their extra fuel (3 liters and 5 liters) to the third vehicle, which is enough for it to travel the remaining 5 kilometers.

Therefore, only one refueling stop is required.