Python gcd for list

Question

I want to calculate gcd for a list of numbers. But I don't know what's wrong with my code.

A = [12, 24, 27, 30, 36]


def Greatest_Common_Divisor(A):
    for c in A:
        while int(c) > 0:
            if int(c) > 12:
                c = int(c) % 12
            else:
                return 12 % int(c)
    print Greatest_Common_Divisor(A)

Nester

Questions seeking debugging help ("why isn't this code working?") must include the desired behavior, a specific problem or error and the shortest code necessary to reproduce it in the question itself. Questions without a clear problem statement are not useful to other readers. – Breeches

This question shows that it's already implemented in the standard library. Just use from fractions import gcd. – Stormi

Also, as soon as that return 12 % int(c) statement executes, the function ends. Did you mean to perhaps be using generators? – Stormi

Answer 1

As of python 3.9, python got built-in support for calculating gcd over a list of numbers.

import math
A = [12, 24, 27, 30, 36]
print(math.gcd(*A))

Output:

3

Wore

Answer 2

here is the piece of code, that I used:

from fractions import gcd
from functools import reduce
def find_gcd(list):
    x = reduce(gcd, list)
    return x

Gynandrous

I got a warning that fractions.gcd is deprecated. Using math.gcd is now recommended. – Robillard

from math import gcd at python 3. – Selfassured

Answer 3

def gcd (a,b):
    if (b == 0):
        return a
    else:
         return gcd (b, a % b)
A = [12, 24, 27, 30, 36]
res = A[0]
for c in A[1::]:
    res = gcd(res , c)
print res

ideone link

Herstein

Answer 4

I used this piece of code:

def gcd(my_list):
    result = my_list[0]
    for x in my_list[1:]:
        if result < x:
            temp = result
            result = x
            x = temp
        while x != 0:
            temp = x
            x = result % x
            result = temp
    return result 

Euthanasia

Answer 5

If you'd like to use an existing method try `np.gcd.reduce':

import numpy as np

A = [12, 24, 27, 30, 36]

print(np.gcd.reduce(A))

which returns 3

Louisville

Its giving WA on list len > 100000 – Nutmeg

@Nutmeg Tell us more! This works for me with a length of 1,000,000 np.gcd.reduce((6060842*np.random.rint(1, 10000000, 1000000)).tolist()) returns 6060842 using numpy 1.19.2 What exactly is the test for which it is failing for you? What version of numpy are you using? What other gcd methods are passing your test that this fails? – Louisville

I am using this on Codechef(CP site in India) where it is passing tests cases where length is < 1000 but further on Original Constraints it is Giving WA. – Nutmeg

@Nutmeg I see, "WA" = Wrong Answer. I went to the site and tried to run it i.stack.imgur.com/5iHu7.png and I couldn't import numpy i.stack.imgur.com/Mi4fu.png so I couldn't even test it there. I'm not sure how Python runs on the site, but this method seems fine when running locally on a computer. I don't know exactly why you get "WA" but that seems to be related to Codechef, it's not a Python message. By the way, my original is a typo, it's np.random.randint not ...rint – Louisville

for running python on Codechef run code under try and except and thx for help ... it may be some other Reason for WA .further the question here ---"codechef.com/JULY21C/problems/MINNOTES" – Nutmeg

Answer 6

It's not clear to me why you are using 12 in your function? Do you want to test your algorithm with 12 specifically?

There is built in function that provides a good solution (fraction.gcd()) as referenced in this answer

If you want to develop your own approach, you could do it this way: sort the list and get the minimum number of list (call it min). Loop from 2 to min, you can get the great common divisor of your list.

Kazue

Answer 7

import functools as f
A = [12, 24, 27, 30, 36]
g = lambda a,b:a if b==0 else g(b,a%b)   #Gcd for two numbers
print(f.reduce(lambda x,y:g(x,y),A))     #Calling gcd function throughout the list.

"Lambda" is an anonymous function where 'g' is assigned with GCD of two numbers whenever called.

"Reduce" is a function in "functools" module which is used to perform a particular function to all of the elements in the list. Here reduce() computes the GCD of the complete list A by computing GCD of first two elements, then the GCD of 3rd element with previously computed GCD of first two elements and so on.

Hope this clears your doubt.

Undercurrent

From review: could you please add more explanation as for why this solves the problem? – Wrist

Hey, yes I have added more explanation on how this solves the problem. – Undercurrent

Answer 8

return exits the function. Inside a for-loop this is normally not intended.

Engineer

Answer 9

As I see your code will simply go in infinite loop. Since you call method Greatest_Common_Divisor recursively but without base case. Align print Greatest_Common_Divisor(A) and "def" in the same column and that problem would be solved. But still what your code does for each number ai, it takes remainder of ai % 12, and then simply print 12 % (ai % 12), and there is no any connection between it and greatestCommonDivisor. Here is simple code for gcd(a,b) which you can use for the whole array:

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

Tambratamburlaine

Answer 10

from functools import reduce
def gcd(a,b):
    if a==0:
        return b 
    else:
        return gcd(b%a,a)
A = [12, 24, 27, 30, 36]
gcdp = reduce(lambda x,y:gcd(x,y),A)
print(gcdp)

I guess this one will clear your doubts.

Badlands

Answer 11

gcd of a list input by the user which can be used for any number of input values.

 n = int(input('enter no of numbers: '))
a = list(map(int,input('enter numbers to find gcd: ').strip().split()))[:n]

def gcd(num1,num2):
    x = 1
    while x:
        if max(num1,num2) % min(num1,num2) == 0:
            return min(num1,num2)
            x = 0
        else :
            r = max(num1,num2)%min(num1,num2)
            return gcd(max(num1,num2),r)

while True:
        a[0] = gcd(a[0],a[1])
        a.pop(1)
        if len(set(a))>2:
            a.pop(2)
        if len(set(a)) == 1:
            break
a = set(a)
print(a)

Learning

Answer 12

def find_gcd(l):
    def gcd(a, b):
        while b:
            a, b = b, a%b
        return a
    n =1
    f = l[0]
    while n != len(l):
        f = gcd(f,l[n])
        if  f == 1:
            return 1
        else:
            n = n + 1          
    return f

l = [12, 24, 27, 30, 36]
print(find_gcd(l))

Sonneteer