LeetCode 2739 - Total Distance Traveled

LeetCode Problem 2739

Difficulty: 🟢 Easy
Topics: Math, Simulation

Solution

Problem Understanding

This problem asks us to compute the maximum total distance a truck can travel given fuel stored in two tanks:

• mainTank, the truck's primary fuel tank.
• additionalTank, a reserve tank that can transfer fuel into the main tank under specific conditions.

The truck consumes fuel at a fixed mileage of 10 kilometers per liter. The interesting part of the problem is the fuel transfer rule:

Whenever the truck uses exactly 5 liters from the main tank, if the additional tank still has at least 1 liter, then 1 liter is immediately transferred into the main tank.

The transfer is not continuous. It only occurs at discrete moments, specifically after every full batch of 5 liters consumed from the main tank.

The goal is to return the maximum distance the truck can travel before all usable fuel is exhausted.

For example, if the truck starts with 5 liters in the main tank and 10 liters in the additional tank:

• The truck spends 5 liters and travels 50 km.
• Because exactly 5 liters were consumed and the additional tank still has fuel, 1 liter is transferred.
• The truck can then travel another 10 km.

The total becomes 60 km.

Constraints Analysis

The constraints are:

• 1 <= mainTank, additionalTank <= 100

These values are very small, which means even a direct simulation would be perfectly acceptable. Since the maximum fuel involved is only 200 liters in total, there is no concern about performance.

However, even though brute force is feasible, we can still derive a cleaner mathematical simulation that avoids unnecessary iteration.

Important Edge Cases

One important edge case occurs when mainTank < 5. In this situation, no transfer can ever happen because the truck never consumes a full batch of 5 liters. The answer is simply mainTank * 10.

Another important case happens when the additional tank runs out before all possible transfers occur. Even if the main tank continues to have enough fuel for more 5-liter batches, transfers stop once additionalTank == 0.

A subtle case is when consuming 5 liters would leave the main tank empty. Since the transfer happens immediately after spending those 5 liters, the truck may still receive fuel and continue moving.

Approaches

Brute Force Approach

A straightforward way to solve the problem is to simulate fuel consumption one liter at a time.

We repeatedly:

1. Consume 1 liter from the main tank.
2. Add 10 km to the total distance.
3. Track how many liters have been consumed since the last transfer.
4. Every time 5 liters are consumed, transfer 1 liter from the additional tank if available.

This approach works because it exactly follows the problem statement and models the truck's behavior step by step.

However, this simulation performs more operations than necessary. Since transfers only matter after every 5 liters, processing one liter at a time introduces unnecessary overhead.

Optimal Approach

The key observation is that transfers happen only after groups of 5 liters consumed.

Instead of simulating each liter individually, we can process fuel in chunks:

• As long as the main tank contains at least 5 liters, consume exactly 5.
• Add 50 km to the answer.
• If additional fuel exists, transfer 1 liter into the main tank.
• Repeat until fewer than 5 liters remain.

Finally, consume whatever fuel is left in the main tank and convert it directly into distance.

This approach is simpler and more efficient because it only processes meaningful events, namely each 5-liter threshold.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(mainTank + additionalTank)	O(1)	Simulates fuel usage one liter at a time
Optimal	O(mainTank / 5)	O(1)	Processes fuel in 5-liter chunks

Algorithm Walkthrough

1. Initialize a variable distance to 0. This will store the total kilometers traveled.
2. While the main tank contains at least 5 liters, consume exactly 5 liters from it. Since the truck travels 10 km per liter, add 50 km to the distance.
3. After consuming 5 liters, check whether the additional tank still has fuel. If it does, transfer 1 liter from the additional tank into the main tank. This models the problem's transfer rule exactly.
4. Repeat this process until the main tank contains fewer than 5 liters. At this point, no further transfers are possible because transfers only occur after consuming a complete 5 liters.
5. Add the distance contributed by the remaining fuel in the main tank using mainTank * 10.
6. Return the total distance.

Why it works

The algorithm works because it preserves the exact behavior described in the problem. Every possible transfer occurs immediately after consuming a valid 5-liter batch, and no transfer is skipped or applied incorrectly. Since the truck only gains fuel at these discrete checkpoints, processing fuel in 5-liter chunks produces the same result as a detailed per-liter simulation while using fewer steps.

Python Solution

class Solution:
    def distanceTraveled(self, mainTank: int, additionalTank: int) -> int:
        distance = 0

        while mainTank >= 5:
            mainTank -= 5
            distance += 50

            if additionalTank > 0:
                mainTank += 1
                additionalTank -= 1

        distance += mainTank * 10

        return distance

The implementation follows the algorithm directly.

The variable distance keeps track of the total kilometers traveled. The while loop continues as long as the truck can spend a full 5 liters from the main tank.

Inside the loop, we subtract 5 liters and add 50 km to the total distance. Then we check whether the additional tank still contains fuel. If it does, we immediately transfer 1 liter to the main tank and decrement the reserve tank.

Once the main tank contains fewer than 5 liters, the loop ends because no further transfers are possible. The remaining fuel is converted directly into distance using mainTank * 10.

This implementation exactly mirrors the truck's fueling behavior.

Go Solution

func distanceTraveled(mainTank int, additionalTank int) int {
    distance := 0

    for mainTank >= 5 {
        mainTank -= 5
        distance += 50

        if additionalTank > 0 {
            mainTank++
            additionalTank--
        }
    }

    distance += mainTank * 10

    return distance
}

The Go implementation is almost identical to the Python version. Since all values are small integers, there is no concern about integer overflow.

Go uses a for loop instead of Python's while, but the logic remains unchanged. No additional data structures are required, and the solution maintains constant space usage.

Worked Examples

Example 1

Input: mainTank = 5, additionalTank = 10

Step	mainTank	additionalTank	Distance	Action
Initial	5	10	0	Start
Consume 5L	0	10	50	Travel 50 km
Transfer 1L	1	9	50	Additional tank injects fuel
Remaining fuel	1	9	60	Travel final 10 km

Final answer: 60

Example 2

Input: mainTank = 1, additionalTank = 2

Step	mainTank	additionalTank	Distance	Action
Initial	1	2	0	Start
Remaining fuel	0	2	10	Travel 10 km

Final answer: 10

Complexity Analysis

Measure	Complexity	Explanation
Time	O(mainTank / 5)	Each loop iteration consumes 5 liters from the main tank
Space	O(1)	Only a few integer variables are used

The runtime depends on how many times the truck can consume a full batch of 5 liters. Since each iteration removes 5 liters, the number of iterations is proportional to mainTank / 5. Given the problem constraints, this is extremely efficient. The space complexity remains constant because no auxiliary data structures are allocated.

Test Cases

solution = Solution()

assert solution.distanceTraveled(5, 10) == 60  # Provided example 1
assert solution.distanceTraveled(1, 2) == 10  # Provided example 2

assert solution.distanceTraveled(4, 100) == 40  # No transfer possible
assert solution.distanceTraveled(5, 0) == 50  # No additional fuel available
assert solution.distanceTraveled(9, 1) == 100  # Exactly one transfer
assert solution.distanceTraveled(10, 2) == 120  # Multiple transfers
assert solution.distanceTraveled(15, 3) == 180  # Several injections
assert solution.distanceTraveled(100, 100) == 1240  # Maximum bounds stress test
assert solution.distanceTraveled(6, 1) == 70  # Transfer after first 5 liters
assert solution.distanceTraveled(11, 1) == 120  # Remaining fuel after one transfer

Test	Why
(5, 10)	Verifies the first provided example
(1, 2)	Verifies the second provided example
(4, 100)	Ensures no transfer happens when main tank is below 5
(5, 0)	Confirms behavior with no reserve fuel
(9, 1)	Tests a single transfer
(10, 2)	Verifies multiple transfers
(15, 3)	Ensures repeated transfers are handled correctly
(100, 100)	Stress test using maximum input values
(6, 1)	Confirms transfer after exactly 5 liters
(11, 1)	Verifies leftover fuel handling

Edge Cases

One important edge case occurs when the main tank starts with fewer than 5 liters, such as mainTank = 4. Since transfers only occur after consuming a full 5 liters, no fuel can ever be injected from the additional tank. A buggy implementation might incorrectly transfer fuel anyway. Our implementation avoids this because the loop only runs while mainTank >= 5.

Another edge case happens when the additional tank is empty from the start, such as mainTank = 5, additionalTank = 0. The truck still consumes fuel normally, but no transfer occurs after the first 5 liters. The conditional check if additionalTank > 0 ensures that transfers happen only when reserve fuel exists.

A subtle edge case occurs when consuming exactly 5 liters empties the main tank, for example mainTank = 5, additionalTank = 1. A naive implementation might stop immediately after reaching zero fuel. However, the problem specifies that the transfer happens immediately after spending 5 liters. Our solution handles this correctly because it performs the transfer before checking whether the loop should terminate.

A final edge case is when the additional tank runs out before the main tank. For example, mainTank = 20, additionalTank = 1 allows only one transfer even though multiple 5-liter consumption events occur. The implementation correctly stops transferring once additionalTank reaches zero.