Question

USING PYTHON 3

Write a function no_pairs(L) that consumes a list of natural numbers L and mutates it, replacing any natural numbers which appear exactly twice in the list with -1. The no_pairs function returns None. This function should run in at worst O(n log n) time.

HINT: Solving this problem within the demanded runtime will likely require both O(n log n) sorting and O(log n) searching!

Samples: L = [254 , 955 , 198 , 590 , 368] after no_pairs ( L ) , L == [254 , 955 , 198 , 590 , 368] L = [42 , 0 , 42 , 12 , 6000 , 1] after no_pairs ( L ) , L == [ -1 , 0 , -1 , 12 , 6000 , 1] L = [4 , 4 , 4 , 2 , 1 , 2 , 1] after no_pairs ( L ) , L == [4 , 4 , 4 , -1 , -1 , -1 , -1]

Answer 1

Screenshot of code:

output:

code:

def L_search(A,x):
low=0
high=len(A)-1
while(low<=high):
mid=(low+high)//2
if A[mid]==x:
if mid==0:
return mid
elif A[mid-1]==x:
high=mid-1
else:
return mid
elif A[mid]<x:
low=mid+1
else:
high=mid-1
return low
def R_search(A,x):
low=0
high=len(A)-1
while(low<=high):
mid=(low+high)//2
if A[mid]==x:
if mid==len(A)-1:
return mid
elif A[mid+1]==x:
low=mid+1
else:
return mid
elif A[mid]<x:
low=mid+1
else:
high=mid-1
return low
def no_pairs(A,L):
for i in range(len(L)):
left=L_search(A,L[i])
right=R_search(A,L[i])
if right==left+1:
L[i]=-1
print(L)
L=[]
print("Enter list: ",end=" ")
L = list(map(int, input().split()))
A=[]
for i in range(len(L)):
A.append(L[i])
A.sort()
print("Mutated list is: ",end=" ")
no_pairs(A,L)

#please upvote.