More test cases are needed


  • 3
    A

    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.


  • 0
    K

    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;
    }

  • 0

    Thanks for pointing this out, I've added your test case.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.