Monday, March 12, 2012

GCD


Here is another simple program of greatest common divisor (GCD) implementation -

Euclid's Algorithm:

while m is greater than zero:
   If n is greater than m, swap m and n.
   Subtract n from m.
n is the GCD

Simple python code :)

import sys

line = sys.stdin.readline()
[n,m] = line.split(None)
n = int(n)
m = int(m)

def gcd(n,m):
    while(m > 0):
        if(n > m):
            t = m
            m = n
            n = t
        m = m - n
    print n

gcd(n,m)

Sample Input/Output

$ python gcd.py
6 15
3
$ python gcd.py
17 8
1
$ python gcd.py
27 9
9

Wednesday, March 7, 2012

K Diff


Given N numbers , [N<=10^5] we need to count the total pairs of numbers that have a difference of K. [K>0 and K<1e9]


In below code k is difference and num is list/set
#Code -
def kdiff(k, num):
        print k
        print num
        a = []
        for i in range(len(num)):
                a.append(num[i]+k)

        print a
        result = set(n).intersection(set(a))
        print result
        print len(result)

#Output -
>>> f = kdiff.kdiff(2, [1,5,3,4,2])
2
[1, 5, 3, 4, 2]
[3, 7, 5, 6, 4]
set([3, 4, 5])
3
>>> f = kdiff.kdiff(1, [363374326, 364147530, 61825163, 1073065718, 1281246024, 1399469912, 428047635, 491595254, 879792181, 1069262793 ])
1
[363374326, 364147530, 61825163, 1073065718, 1281246024, 1399469912, 428047635, 491595254, 879792181, 1069262793]
[363374327, 364147531, 61825164, 1073065719, 1281246025, 1399469913, 428047636, 491595255, 879792182, 1069262794]
set([])
0