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

[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