Index out of bounds

[code-reaper08]

Getting list index out of bound in this line, on execution.

[Chandu71202]

Hey code-reaper08 That list index out of bound is due to reason:

1. For any number you choose atleast the number "1" will be the GCD (in case of prime numbers).
2. Suppose the number are 18 and 76 as you mentioned here its better to take 2 for loops for m and n
3. Now lets see the control flow. max is 76 . For loops gets the range as 76. enter the loop and checks 18%1==0. Its true and appends 1 in fm array and it won't checks the elif since if satisfied. And next iteration value goes with 2 . But 76%1==0 which is true and fn must append with 1 that haven't been done.
4. Not only 1 any number which gets divisible by both given numbers won't append in fm and fn Here while checking the same elements no element appends and it remains as a empty list. hence cf[0] is out of index
5. And another point to consider we need the product of all common divisors of both number for GCD. not just the first element

Check this out :)

import math
def gcd(m,n):
    fm = []
    fn = []
    cf = []
    for i in range(1,m): 
        if (m % i) == 0:
            fm.append(i) # add to fm
    for i in range(1,n):        
        if ( n % i) == 0:
             fn.append(i) # add to fn
    for f in fm:
         if f in fn:
            cf.append(f) # add to cf
    return(math.prod(cf))

# driver code
print(gcd(18,76))

[code-reaper08]

Awesome @Chandu71202

Looks cool 😎 Will check it out and replace the necessary.

[code-reaper08]

Awesome @Chandu71202

Looks cool 😎 Will check it out and replace the necessary.

Hey @Chandu71202 😄

I made this using single loop, the problem is elif as you told, we won't need the math module I guess. we can use negative index as used in lecture.

def gcd(m,n):
    fm = []
    fn = []
    cf = []
    for i in range(1,max(m,n)): #single loop instead of two for loops.
        if (m % i) == 0:
            fm.append(i) # add to fm
        if ( n % i) == 0:
            fn.append(i) # add to fn
    for f in fm:
        if f in fn:
            cf.append(f) # add to cf
    return(cf[-1])

# driver code
print(gcd(18,76))

Now it works, look once in your system.

Look at this commit

4acc428e35256b8b7162c1384cded8d58e475337

[code-reaper08]

5. And another point to consider we need the product of all common divisors of both number for GCD. not just the first element

@Chandu71202 I think product is not needed, we just need the largest common factor between m & n, so

import math
def gcd(m,n):
    fm = []
    fn = []
    cf = []
    for i in range(1,m): 
        if (m % i) == 0:
            fm.append(i) # add to fm
    for i in range(1,n):        
        if ( n % i) == 0:
             fn.append(i) # add to fn
    for f in fm:
         if f in fn:
            cf.append(f) # add to cf
    return(math.prod(cf))

# driver code
print(gcd(98,56))

This gives me an output of 196.

Whereas here we get GCD as

def gcd(m,n):
    fm = []
    fn = []
    cf = []
    for i in range(1,max(m,n)): #single loop instead of two for loops.
        if (m % i) == 0:
            fm.append(i) # add to fm
        if ( n % i) == 0:
            fn.append(i) # add to fn
    for f in fm:
        if f in fn:
            cf.append(f) # add to cf
    return(cf[-1])

# driver code
print(gcd(98,56))

This gives the GCD as 14

[Chandu71202]

Ohh yeah code-reaper08. That's correct no need of using the product. And using a single for loop is too a getting a less space which was good. I think the updated one is good to go👌

[code-reaper08]

Awesome then 😄

I've added two more optimizations according to the lectures. You can have a look, there is an another open issue here #2 on addition of new algorithm too. You can work on that too if you wish :-)

Cheers !

[code-reaper08]

I'll close this issue, since its solved 🥇