How to convert this Python code to C++

Question

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

Well, a quick solution would be to use `long long`. That doesn't mean larger values are all safe, though. — chris, Feb 22 '14 at 21:35
But is `N*M` in range? You could try using `long long`; on your platform `int` and `long` might be the same size. — Joe, Feb 22 '14 at 21:36
Possible duplicate of [Convert Python program to C/C++ code?](https://stackoverflow.com/q/4650243/608639) — jww, Nov 21 '19 at 13:39

barak manos · Answer 1 · 2014-02-22T21:46:05.460

1

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++.

edited Feb 22 '14 at 21:46

answered Feb 22 '14 at 21:35

barak manos

29,648
10
62
114

I've tried multiple combinations of this approach and it still doesn't seem to work. – jaho Feb 22 '14 at 21:49
You didn't say why this approach doesn't work, Marian. Are you getting a compile error with `long long`? That's not part of C++03, but it is a fairly standard extension. It is part of C++11. – David Hammen Feb 22 '14 at 22:08
No compile time errors, but the result is still incorrect. You can test it for yourself here: https://codility.com/demo/take-sample-test/chocolates_by_numbers – jaho Feb 22 '14 at 22:23
The problem is that `int lcm = (int) (m/g)` is incorrect. It needs to be `long long lcm = m / g`. – David Hammen Feb 22 '14 at 23:16
Well, as I said in the answer, you might as well change every `int` in your code to `unsigned long long`. – barak manos Feb 23 '14 at 05:48

David Hammen · Accepted Answer · 2014-02-22T21:51:13.893

1

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

edited Feb 22 '14 at 21:51

answered Feb 22 '14 at 21:43

David Hammen

32,454
9
60
108

This is it, well spotted! I hate missing stuff like that. Error handling is not necessary as both M and N are guaranteed to be at least 1. – jaho Feb 22 '14 at 21:51
Though the answer avoids the problem in OP solution, this doesn't highlight the problem in that. Its better to know the actual problem that exists in OP solution. The mistake is very common which is often overlooked. – Shashwat Kumar Feb 22 '14 at 22:36
The intent should be 'why my solution does not work' rather than 'just give me the correct solution'. – Shashwat Kumar Feb 22 '14 at 22:46

Shashwat Kumar · Answer 3 · 2014-02-22T21:45:05.640

-1

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

edited Feb 22 '14 at 21:45

answered Feb 22 '14 at 21:36

Shashwat Kumar

5,159
2
30
66

How to convert this Python code to C++

3 Answers3