Total Distance Traveled
EasyPrompt
A truck has two fuel tanks. You are given two integers, mainTank representing the fuel present in the main tank in liters and additionalTank representing the fuel present in the additional tank in liters.
The truck has a mileage of 10 km per liter. Whenever 5 liters of fuel get used up in the main tank, if the additional tank has at least 1 liters of fuel, 1 liters of fuel will be transferred from the additional tank to the main tank.
Return the maximum distance which can be traveled.
Note: Injection from the additional tank is not continuous. It happens suddenly and immediately for every 5 liters consumed.
Example 1:
Input: mainTank = 5, additionalTank = 10
Output: 60
Explanation:
After spending 5 litre of fuel, fuel remaining is (5 - 5 + 1) = 1 litre and distance traveled is 50km.
After spending another 1 litre of fuel, no fuel gets injected in the main tank and the main tank becomes empty.
Total distance traveled is 60km.Example 2:
Input: mainTank = 1, additionalTank = 2
Output: 10
Explanation:
After spending 1 litre of fuel, the main tank becomes empty.
Total distance traveled is 10km.
Constraints:
1 <= mainTank, additionalTank <= 100
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. We use a loop to model the truck's journey in chunks. In each step, the truck consumes 5 liters of fuel, and if the additional tank is not empty, 1 liter is transferred back to the main tank. This process repeats until the main tank has less than 5 liters, after which the remaining fuel is consumed to cover the final distance.
Algorithm
-
- Initialize a variable
distanceto 0.
- Initialize a variable
-
- Start a
whileloop that continues as long asmainTankhas 5 or more liters.
- Start a
-
- Inside the loop, simulate the consumption of 5 liters:
- Decrement
mainTankby 5. - Increment
distanceby 50 (since mileage is 10 km/l).
-
- Check if the
additionalTankhas fuel (additionalTank > 0).
- If it does, transfer 1 liter by incrementing
mainTankby 1 and decrementingadditionalTankby 1.
- Check if the
-
- Once the loop finishes,
mainTankwill have less than 5 liters.
- Once the loop finishes,
-
- Calculate the distance from the remaining fuel by adding
mainTank * 10todistance.
- Calculate the distance from the remaining fuel by adding
-
- Return the total
distance.
- Return the total
Walkthrough
The simulation approach iteratively calculates the total distance. We track the fuel in both tanks and the total distance traveled. The core of the logic is a while loop that executes as long as the mainTank contains at least 5 liters, which is the threshold for a potential fuel transfer.
Inside the loop, we subtract 5 liters from the mainTank and add 50 km to our total distance. Then, we check the additionalTank. If it has fuel, we simulate the transfer of 1 liter to the mainTank. This cycle of consuming 5 liters and potentially gaining 1 liter continues. After the loop terminates, any fuel left in the mainTank (which will be less than 5 liters) is used up, and the corresponding distance is added to the total.
class Solution { public int distanceTraveled(int mainTank, int additionalTank) { int distance = 0; while (mainTank >= 5) { // Consume 5 liters from the main tank mainTank -= 5; distance += 50; // Transfer 1 liter from additional tank if possible if (additionalTank > 0) { mainTank += 1; additionalTank -= 1; } } // Add distance from remaining fuel in the main tank distance += mainTank * 10; return distance; }}Complexity
Time
O(mainTank). In each iteration of the loop, the `mainTank`'s fuel decreases by a net of 4 liters (5 consumed, 1 added). Therefore, the number of iterations is proportional to the initial amount of fuel in the main tank. Given the constraint `mainTank <= 100`, this is very fast.
Space
O(1). The algorithm uses a fixed number of variables to store the state (`mainTank`, `additionalTank`, `distance`), so the space complexity is constant.
Trade-offs
Pros
It is straightforward to understand and implement as it directly follows the problem statement.
It is guaranteed to be correct for the given constraints.
Cons
Less efficient than a direct mathematical solution because it involves a loop.
For significantly larger constraints, this approach might become too slow.
Instead of simulating the process step-by-step, we can derive a direct mathematical formula to solve the problem in a single calculation. By analyzing the fuel dynamics, we can determine the exact number of times fuel will be transferred from the additional tank. This allows us to calculate the total effective fuel that can be burned and, consequently, the total distance, without any loops.
Algorithm
-
- Determine the maximum number of times a fuel transfer can occur. A transfer requires consuming 5 liters, which results in a net loss of 4 liters from the main tank. The number of times the main tank can sustain this is
(mainTank - 1) / 4.
- Determine the maximum number of times a fuel transfer can occur. A transfer requires consuming 5 liters, which results in a net loss of 4 liters from the main tank. The number of times the main tank can sustain this is
-
- The number of actual transfers is also limited by the fuel in the
additionalTank. So, the number of transfers isactualTransfers = min((mainTank - 1) / 4, additionalTank).
- The number of actual transfers is also limited by the fuel in the
-
- Each transfer effectively adds 1 liter to the total fuel that can be burned throughout the journey. The total distance is derived from the total fuel burned, which is the initial
mainTankplus theactualTransfers.
- Each transfer effectively adds 1 liter to the total fuel that can be burned throughout the journey. The total distance is derived from the total fuel burned, which is the initial
-
- Calculate the total distance using the formula:
distance = (mainTank + actualTransfers) * 10.
- Calculate the total distance using the formula:
-
- Return the result.
Walkthrough
This O(1) approach relies on a mathematical insight into the fuel consumption process. A fuel transfer occurs every time 5 liters are consumed. When a transfer happens, 5 liters are removed, and 1 is added, leading to a net decrease of 4 liters in the mainTank.
To sustain r transfers, the mainTank must be large enough to handle this net loss r times. The condition for r transfers is mainTank + (r-1) >= 5*r, which simplifies to r <= (mainTank - 1) / 4. This gives us the maximum number of transfers the mainTank can support.
The actual number of transfers is, of course, also limited by the amount of fuel in the additionalTank. So, actualTransfers = Math.min(additionalTank, (mainTank - 1) / 4).
The total distance traveled is based on the total fuel burned. We can prove that the total distance is 10 * (mainTank + actualTransfers). For each of the actualTransfers, we travel 50km. The remaining fuel covers the rest of the distance. The sum simplifies to this neat formula.
class Solution { public int distanceTraveled(int mainTank, int additionalTank) { // Calculate the maximum number of transfers the main tank can sustain. // To perform 'r' transfers, we need to burn 5*r liters. // This fuel comes from the initial mainTank and (r-1) previous transfers. // So, mainTank + (r-1) >= 5*r => mainTank - 1 >= 4*r => r <= (mainTank - 1) / 4. int maxTransfers = (mainTank - 1) / 4; // The actual number of transfers is also limited by the additionalTank. int actualTransfers = Math.min(additionalTank, maxTransfers); // The total distance can be shown to be 10 * (mainTank + actualTransfers). return (mainTank + actualTransfers) * 10; }}Complexity
Time
O(1). The solution consists of a few arithmetic operations, which take constant time regardless of the input values.
Space
O(1). Only a few variables are needed for the calculation, so the space usage is constant.
Trade-offs
Pros
Extremely efficient, providing the solution in constant time, O(1).
The code is very concise and elegant.
Cons
The derivation of the mathematical formula is not immediately obvious and requires careful reasoning.
Solutions
Solution
class Solution { public int distanceTraveled ( int mainTank , int additionalTank ) { int ans = 0 , cur = 0 ; while ( mainTank > 0 ) { cur ++; ans += 10 ; mainTank --; if ( cur % 5 == 0 && additionalTank > 0 ) { additionalTank --; mainTank ++; } } return ans ; } }var distanceTraveled = function ( mainTank , additionalTank ) { let ans = 0 , cur = 0 ; while ( mainTank ) { cur ++ ; ans += 10 ; mainTank -- ; if ( cur % 5 === 0 && additionalTank ) { additionalTank -- ; mainTank ++ ; } } return ans ; };class Solution { public: int distanceTraveled ( int mainTank , int additionalTank ) { int ans = 0 , cur = 0 ; while ( mainTank > 0 ) { cur ++ ; ans += 10 ; mainTank -- ; if ( cur % 5 == 0 && additionalTank > 0 ) { additionalTank -- ; mainTank ++ ; } } return ans ; } };class Solution : def distanceTraveled ( self , mainTank : int , additionalTank : int ) -> int : ans = cur = 0 while mainTank : cur += 1 ans += 10 mainTank -= 1 if cur % 5 == 0 and additionalTank : additionalTank -= 1 mainTank += 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.