Greedy, Bit Manipulation and Math

The greedy-choice property (a locally optimal choice leads to a global optimum) and optimal substructure.

A proof technique showing any optimal solution can be transformed, step by step, into the greedy solution without getting worse.

Greedy picks 4 + 1 + 1 (3 coins) but 3 + 3 (2 coins) is optimal, so DP is needed for arbitrary coin systems.

Repeatedly merge the two least-frequent nodes using a min-heap until one tree remains: O(n log n).

Track the farthest reachable index; if any index exceeds it, return false.

If total gas ≥ total cost, a solution exists; start after any point where the running tank goes negative.