CODEWITHSUNDEEP
pythonc++integeroverflow
jaho
jaho

Reputation: 4992

How to convert this Python code to C++

I have a working algorithm in Python which I want to convert to C++:

def gcd(a, b):    
    if (a % b == 0):
        return b
    else:
        return gcd(b, a % b)

def solution(N, M):
    lcm = N * M / gcd(N, M)
    return lcm / M

I'm having a problem with large input values as the multiple of N and M causes integer overflow and using long to store its value doesn't seem to help, unless I'm doing something wrong.

Here's my current code:

int gcd(int a, int b)
{
    if (a % b == 0)
        return b;
    else
        return gcd(b, a % b);
}

int solution(int N, int M) {

    // Calculate greatest common divisor
    int g = gcd(N, M);

    // Calculate the least common multiple
    long m = N * M;
    int lcm = m / g;

    return lcm / M;
}

Upvotes: 0

Views: 147

Answers (3)

David Hammen
David Hammen

Reputation: 33106

You are computing g=gcd(N,M), then m=N*M, then lcm=m/g, and finally returning lcm/M. That's the same as returning N/gcd(N,M). You don't need those intermediate calculations. Get rid of them. Now there's no problem with overflow (unless M=0, that is, which you aren't protecting against).

int solution(int N, int M) {
   if (M == 0) {
      handle_error();
   }
   else {
      return N / gcd(N,M);
   }
}

Upvotes: 1

barak manos
barak manos

Reputation: 30136

To begin with, change:

long m = N * M;
int lcm = m / g;

To:

long long m = (long long)N * M;
int lcm = (int)(m / g);

In general, you might as well change every int in your code to unsigned long long...

But if you have some BigInt class at hand, then you might want to use it instead.

Here is one for free: http://planet-source-code.com/vb/scripts/ShowCode.asp?txtCodeId=9735&lngWId=3

It stores a natural number of any conceivable size, and supports all arithmetic operators provided in C++.

Upvotes: 1

Shashwat Kumar
Shashwat Kumar

Reputation: 5287

The problem is in long m = N*M. The multiplication takes place as 32 bit integers only. Since both are of int type, overflow occurs.

Correction is long long m = (long long)N*M

Upvotes: -1

Related Questions