0

Consider the following buggy code for the Gas Station problem. Which line contains the subtle bug that can cause incorrect results?

medium🐞 Bug Identification Q14 of Q15

Greedy Algorithms - Gas Station (Circular)

Consider the following buggy code for the Gas Station problem. Which line contains the subtle bug that can cause incorrect results?

def canCompleteCircuit(gas, cost):
    n = len(gas)
    net = [gas[i] - cost[i] for i in range(n)]
    # Bug: missing total gas check
    prefix = [0] * (2 * n + 1)
    for i in range(2 * n):
        prefix[i+1] = prefix[i] + net[i % n]
    for i in range(n):
        if prefix[i+n] - prefix[i] >= 0:
            return i
    return -1

ALine 3: net array computation

BLine 4: missing total gas vs total cost check

CLine 6: prefix sums computation loop

DLine 8: checking prefix sums for valid start

Step-by-Step Solution

Solution:

Step 1: Identify missing total gas check
The code does not check if sum(net) < 0 before proceeding, which can cause incorrect start index or false positives.
Step 2: Verify other lines
Net array, prefix sums, and prefix difference checks are correct and standard.
Final Answer:
Option B -> Option B
Quick Check:
Missing total gas check leads to incorrect results [OK]

Quick Trick: Always check total gas >= total cost before searching start [OK]

Common Mistakes:

MISTAKES

Forgetting total gas check
Misusing modulo in prefix sums
Resetting start without resetting tank

Trap Explanation:

PITFALL

Without total gas check, code may return invalid start or fail on impossible cases.

Interviewer Note:

CONTEXT

Tests if candidate knows critical early termination condition to avoid wrong answers.

Master "Gas Station (Circular)" in Greedy Algorithms

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions

More Greedy Algorithms Quizzes