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

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

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

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