Given the prefix sums array prefix = [0, 1, 3, 2, 5, 7, 8, 10, 9, 12, 14] computed for net = [1, 2, -1, 3, 2] repeated twice, and the function returns start index 1, what was the original gas and cost difference array net?

hard🔄 Reverse Engineer Q9 of Q15

Greedy Algorithms - Gas Station (Circular)

A[1, -1, 2, 3, 2]

B[2, 1, -1, 3, 2]

C[1, 2, -1, 3, 2]

D[1, 2, 3, -1, 2]

Step-by-Step Solution

Solution:

Step 1: Derive net from prefix differences
net[i] = prefix[i+1] - prefix[i] for i in [0..4]: [1, 2, -1, 3, 2]
Step 2: Check start index 1 validity
Starting at index 1 means the function returns 1 as start, but the original net array is as derived.
Final Answer:
Option C -> Option C
Quick Check:
Prefix differences match net array [OK]

Quick Trick: Prefix differences reveal net array [OK]

Common Mistakes:

MISTAKES

Incorrectly rotating net array based on start index

Trap Explanation:

PITFALL

Candidates often confuse rotation with original net array.

Interviewer Note:

CONTEXT

Tests reverse reasoning from prefix sums and start index

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

Given the prefix sums array prefix = [0, 1, 3, 2, 5, 7, 8, 10, 9, 12, 14] computed for net = [1, 2, -1, 3, 2] repeated twice, and the function returns start index 1, what was the original gas and cost difference array net?

Step 1: Derive net from prefix differences

Step 2: Check start index 1 validity

Final Answer:

Quick Check:

Want More Practice?