vivek_ragi

GAS_STATION

Jul 9th, 2021 (edited)
459
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     //greedy
  4.     int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
  5.         int sumg = 0;
  6.         int sumc = 0;
  7.        
  8.         for (int i = 0; i < gas.size(); ++i) {
  9.             sumg += gas[i];
  10.             sumc += cost[i];
  11.         }
  12.        
  13.         if (sumg < sumc) {
  14.             return -1;
  15.         }
  16.         int total = 0, ans = 0;
  17.         //we know that unique answer exists
  18.         for (int i = 0; i < gas.size(); ++i) {
  19.             total += gas[i] - cost[i];
  20.            
  21.             if (total < 0) {
  22.                 total = 0;
  23.                 ans = i + 1;
  24.             }
  25.         }
  26.        
  27.        
  28.         return ans;
  29.     }
  30. };
RAW Paste Data