More test cases are needed

• The coverage of test cases is quite limit. The following buggy solution
passes all the tests.

``````class Solution {
public:
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
const int n = gas.size();
int balance = 0;
for (int i = 0; i<n; ++i) {
balance+=(gas[i] - cost[i]);
}

if (balance<0) {
return -1;
}

if (n==1) {
return 0;
}

// find index start, which will be a begining of a consequence sequnece stations such that gas[i]-cost[i]>=0
int start = 0;
if (gas[0] - cost[0]<0) {
for (start=1; start<n; ++start) {
if (gas[start] - cost[start] >= 0) {
break;
}
}
if (start == n) {
return -1;
}
} else {
// now start has non-negative gas storage
int pre = n-1;
for (; pre>0; --pre) {
if (gas[pre] - cost[pre] < 0) {
break;
}
}

if (pre == 0) {
return 0;  // or any
}

start = (pre+1) % n;
}

int max_collection = -1;
int start_index = -1;
int saved = 0;
int start_i = start;
for (int i = start, next = start+1; next != start; ++i) {
i %= n;
int d = gas[i] - cost[i];
saved+=d;
next = (i+1) % n;

if (d<0 && (gas[next] - cost[next])>=0) {
if (max_collection<saved) {
max_collection = saved;
start_index = start_i;
start_i = next;  // THIS IS BUGGY; THESE TWO LINES
saved = 0;   //  (cont.) should be after this if block
}
// start_i = next;
// saved = 0;
}
}
return start_index;
}
};
``````

The above code has a bug. However, is passes all the test cases. The bug can be easily detected by
the following test case:

``````vector<int> gas{1,2,3,3};
vector<int> cost{2,1,5,1};
``````

The posted buggy code outputs -1, but the correct answer should be 3.

• yep. and my code pass your test case.

``````int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
// Note: The Solution object is instantiated only once and is reused by each test case.
int left = 0;
int size = gas.size();
int last = size-1;
int count = 0;
for(int i = size-1; i >= 0; i--){
while(count < size){
if(gas[last]+left >= cost[last]){
left += gas[last] - cost[last];
last = (last+1)%size;
count++;
}
else
break;
}
if(count == size)
return i;
else{
if(i == 0 || i-1 == last)
return -1;
left += gas[i-1] - cost[i-1];
count++;
}
}
return -1;
}``````