plz help me to solve Sum of all gcd numbers in an array

+3 votes
asked Aug 31 by ramya Kondapalli (150 points)
k=4

arr[]=3 8 1 10 6 3 1

output=12

expalnation:

GCD of:

(4,3)=1

(4,8)=4

(4,1)=1

(4,10)=2

(4,6)=2

(4,3)=1

(4,1)=1

sum of all GCD is = 1+4+1+2+2+1+1=12

2 Answers

+1 vote
answered Sep 7 by Peter Minarik (7,830 points)

This sounds like a homework and as such, the main goal here is to learn something. So providing you the full solution is actually worse than not helping.

I'd suggest looking up some Python tutorial and reference pages, such as https://www.w3schools.com/python/.

There, you can see the syntax and what functionality is available for you.

General Solution

To solve the problem, you'd need to do the following steps in your code:

  1. iterate through the array (arr) that holds the input numbers
  2. calculate the GCD for all number pair (k and the actually iterated arr element -- arr[i])
  3. Add this calculated GCD to a counter (e.g. sum)
  4. keep repeating 1-3 until reaching the end of arr.
  5. display the result.

Greatest Common Divisor (GCD)

For calculating the GCD there could be various solutions. One of the naive solutions could be this:

  1. loop through integral numbers (backwards) starting from smaller of k or arr[i] (min(k, arr[i])) until you reach 1. Let's call this x for this example.
  2. Try dividing both k and arr[i] with the currently iterated number (x) and check for the reminder. The operator for this is % (modulus). E.g.: reminder = k % x
  3. If the result of modulus with x for both k and arr[i] is 0, then you have a divisor. Since we're going from the largest number toward the smallest, we can be assured we have the greatest common divisor.

Of course, one can optimise this logic or come up with better ones, but this should work for now. You can improve it later, when the program works fine for the generic cases.

After you've done your implementation and have some problem, please, share your code so people can point out if you made any mistakes.

Good luck.

0 votes
answered Sep 21 by Praveen Kumar (180 points)

def GCD(a,b):
    while(b):
        a,b = b, a%b 
    return a

def GCDSUM(k,list1):
    sum = 0
    m = 0
    for i in list1:
        n = GCD(k, list1[m])
        sum += n 
        m += 1
        
    return sum

list1 = [3, 8, 1, 10, 6, 3, 1]
k = 4
x = GCDSUM(k,list1)
print(x)

Welcome to OnlineGDB Q&A, where you can ask questions related to programming and OnlineGDB IDE and and receive answers from other members of the community.
...