My code gives correct solution on local IDE for sample test case: 30 12 , but when I run it on Interview Bit it gives runtime error. Can’t figure out what’s going wrong? Anyone with a piece of advice?
Here’s the code:
int findGCD(int x, int b) { //euclid's algorithm recursive implementation
if (x == 0)
return b;
findGCD(b % x, x);
}
int Solution::cpFact(int A, int B) {
//iterate to sqrt(A) and find all factors
//sort them in ascending order
//euclid’s algorithm to find GCD
int i,j;
vector<int>factors;
for ( i = 1; i <= sqrt(A); ++i) { //storing all factors
if (A % i == 0)
{
factors.push_back(i);
if(A/i!=i)
factors.push_back(A / i);
}
}
sort(factors.begin(), factors.end()); //sorting factors in ascending order
for (auto it = factors.rbegin(); it != factors.rend(); ++it) { //iterating from the reverse side with the largest factors
i = (*it) > B ? B : (*it); // i stores the smallest number and j the bigger number
if (i == *it)
j = B;
else
j = *it;
i = findGCD(i, j);
if (i == 1) //if coprime
return *it;
}
}