Skillrack Inlab Problem 3

Solutions for Skillrack CSE1001 Inlab 3

18-Sept-2016 to 20-Sept-2016

Total time : 15 mins

Challenges : 1

Question (GCD Sorting using functions)

Given a tuple of ‘n’ numbers, call the first number as leader, write an algorithm and subsequent Python code to arrange the other numbers in ascending order of their GCD with the leader. When GCD of more than one elements are equal sort them based on the element. For example, given 10 elements 12, 15, 16, 20, 32, 6, 45, 18, 34, and 67 the output must be the leader followed by other elements in ascending order of their GCD with the leader (i.e.) 12, 67, 34, 15, 45, 16, 20, 32, 6, 18. Write a function to compute GCD of two numbers.

Input Format

First line contains the number of elements in tuple, n

Next ‘n’ lines contains the elements in the tuple

Output Format

Print the leader
Print other elements in increasing order of their GCD with leader

Solution

def gdc(x,y) :
    g=1
    for i in range(1,x+1) :
        if y%i==0 and x%i==0 :
            if i > g :
                g=i
    return(g)
n=int(input())
l=[]
d={}
for i in range(n) :
    x=int(input())
    l.append(x)
led=l[0]
for i in range(1,n) :
    g=gdc(led,l[i])
    if g in d :
        d[g].append(l[i])
    else :
        d[g]=[l[i]]
print(led)
for i in range(1,led+1) :
    if i in d :
        q=d[i]
        q.sort()
        for j in q :
            print(j)

Input/Output

INPUT
10
12
15
16
20
32
6
45
18
34
67

OUTPUT
12
67
34
15
45
16
20
32
6
18

 

Advertisements

One thought on “Skillrack Inlab Problem 3

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s