My solution was right on another compiler/environment, but OJ says it is wrong


  • 0
    Q

    The code below is using the mathmetical permutation calculation, and trying to avoid integer overflow as much as possible.

    For input uniquePaths(9,8), OJ says my answer is 6435*4, which is wrong, but in another environment, the output is exactly 6435.

    Since OJ doesn't support printf/cout, I cannot debug. Does anyone know anything about OJ environment?
    The code below is tested under
    _http://www.compileonline.com/compile_cpp_online.php

    #include <iostream>
    #include <vector>
    using namespace std;
    class Solution { 
    public:
        int uniquePaths(int m, int n) {
            int m2 = m-1;
            if(m2 == 0) return 1;
            int n2 = n-1;
            if (n2 == 0) return 1;
            
            int  ways = 1;
            int limit = (m2 < n2) ? m2 : n2;
            int factor = m2+n2-limit+1;
            int divider = 1;
            int i = 1;
            vector<int> factors(limit);
            for(i =0 ; i < limit; i++) { factors[i] =m2+n2-i; }
                    for(i = limit; i >= 1; i--) {
                int res = (m2+n2)%i; 
                 if (factors[res] >= i) {
                    factors[res] /= i; 
                 } else if (factors[res+i] >= i) {                                     
                     factors[res+i] /= i;
                 } else {
                     divider *= i;
                 }
                
            }
            
            for(i =0; i< limit; i++) {
                ways *= factors[i];
                if(divider > 1) {
                  if ( (ways%divider) ==0) {
                      ways /= divider;
    
                      divider = 1;
                  } 
                }
            }
            
    
            
            return ways;
        }
    };
    
    int main()
    {
       Solution s;
       cout << s.uniquePaths(9,8) << endl;
       return 0;
    }

  • 0
    Q

    I found the problem:

    [res+i] could be >= limit. The environment I used has vector boundary check. Others don't.

    Besides, the factors[res] could be > i but not a multiple of i. So, the right and accepted code should be like this:

    class Solution { 
    public:
        int uniquePaths(int m, int n) {
            int m2 = m-1;
            if(m2 == 0) return 1;
            int n2 = n-1;
            if (n2 == 0) return 1;
            
            int  ways = 1;
            int limit = (m2 < n2) ? m2 : n2;    // the factorial number of the denominator
            int factor = m2+n2-limit+1;    
            int divider = 1;
            int i = 1;
            vector<int> factors(limit);    
            for(i =0 ; i < limit; i++) { factors[i] =m2+n2-i; }    // prepare all the numerator factors
    
           //start from the larget denominator factor, try to cancel it as early as possible.
           //note that for the first 2 to 3 factor, there must be a multiple of them respectively, in the numerrator sequence, since both the numerator and the denominator are composed by multiplying  "limit" numbers 
            //  and the multiple appears at (m2_n2)%i
            for(i = limit; i >= 1; i--) {   
                int res = (m2+n2)%i;    //key step: get the index of the multiple of this de
                 if (factors[res] >= i && (factors[res]%i == 0)) {
                    factors[res] /= i; 
                 } else if (res+i < limit && factors[res+i] >= i && (factors[res+i]%i == 0)) {                                     
                     factors[res+i] /= i;
                 } else {
                     divider *= i;   //cannot find a multiple by now, usually because the factor is used up. usually only happens to  2's multiples
                 }
                
            }
            
            for(i =0; i< limit; i++) {
                ways *= factors[i];
                if(divider > 1) {
                  if ( (ways%divider) ==0) {
                      ways /= divider;
        //              printf("i=%d, ways=%d, divider=%d\n", i, ways, divider);
                      divider = 1;
                  } 
                    else if ( (ways%2==0) && (divider%2==0)) {  //if can divide by 2, then do it
                        ways /= 2;
                        divider /= 2;
                    }              
                }
            }
            
    
            
            return ways;
        }
    };

Log in to reply
 

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