Program to find common between three sorted list in python.
To find common between three sorted list using brute force is take O(n^3) time because brute force use three loop to find common between three sorted list.One loop for each list.
To reduce the complexity optimal solution is use that take O(n) time(because only one loop) to solve the problem.
For example
a=[1,2,3]. b=[2,3,4]. c=[2,4,5]
Common between three sorted list is
2
Method 1 : brute force
def fc(a,b,c):
n=len(a)
m=len(b)
k=len(c)
for i in range(0,n):
for j in range(0,m):
if(a[i]==b[j]):
for k in range(0,k):
if(a[i]==c[k]):
print(a[i])
a=[1,2,3]
b=[2,3,4]
c=[2,3,5]
fc(a,b,c)
Method 2. Find common b/w three sorted list with complexity O(n).
def fc(a,b,c):
n=len(a)
h=len(b)
k=len(c)
x=0
y=0
z=0
while(x<n and y<h and z<k):
if(a[x]==b[y] and a[x]==c[z]):
print(a[x])
x=x+1
y=y+1
z=z+1
else:
if(a[x]==b[y] and a[x]>c[z]):
z=z+1
if(a[x]==c[z] and a[x]>b[y]):
y=y+1
if(b[y]==c[z] and b[y]>a[x]):
x=x+1
if(a[x]>b[y] and a[x]>c[z]):
z=z+1
y=y+1
if(b[y]>a[x] and b[y]>c[z]):
z=z+1
x=x+1
if(c[z]>b[y] and c[z]>a[x]):
y=y+1
x=x+1
a=[1,2,3]
b=[2,3,4]
c=[2,3,5]
fc(a,b,c)
0 Comments