Reputation: 21
I have been given two lists, say list1 and list2. I have to arrange the elements of the list1 in such a way that at particular index the element of list1 is greater than the element of list2. We have to find how many such elements of list1 are there. For example:
list1=[20,30,50]
list2=[60,40,25]
Here only element index 2 is greater i.e. 50>25, but if we swap 50 and 30 in list1 So,
list1=[20,50,30]
list2=[60,40,25]
then 50 > 40 ( at index 1) and 30 > 25 (at index 2). So we got 2 elements 50 and 30 which are greater at their respective index. Here is my approach
def swap(a,b):
a,b=b,a
return a,b
n=3
g=list(map(int,input().split()))
o=list(map(int,input().split()))
c=0
for i in range(n):
if o[i]>g[i]:
for j in range(i+1,n):
if g[j]>o[i]:
g[i],g[j]=swap(g[i],g[j])
c+=1
break
else:
c+=1
print(c)
But for
list1= [3,6,7,5,3,5,6,2,9,1]
list2= [2,7,0,9,3,6,0,6,2,6]
Its giving c=6 but expected output is c=7
Upvotes: 2
Views: 569
Reputation: 17322
list1= [3,6,7,5,3,5,6,2,9,1]
list2= [2,7,0,9,3,6,0,6,2,6]
list1 = sorted(list1)
it = iter(enumerate(list1))
list2 = sorted(list2)
c = next(it)
good = []
for i, n in enumerate(list2 ):
try:
while c[1] < n:
c = next(it)
good.append([i, c[0]])
c = next(it)
except StopIteration:
break
for idx1, idx2 in good:
list1[idx1], list1[idx2] = list1[idx2], list1[idx1]
final_l1_l2 = sum(a > b for a, b in zip(list1, list2))# how many l1 are > l2
print(final_l1_l2)
output:
7
also, you can print list1 and list2 after the rearrange:
print(list1)
print(list2)
output:
[1, 2, 3, 3, 5, 6, 6, 7, 9, 5]
[0, 0, 2, 2, 3, 6, 6, 6, 7, 9]
the idea is to sort both lists and then to check what elements from list1
are greater than the elements from list2
if one element from list1
it is smaller then the current element from list2
just go to the next element from the list1
till there are no more elements in list1
Upvotes: 1
Reputation: 42129
You have to sort the two lists and then run through them to find "matches" where a value of list1 is greater than the next value of list2. This will pair up the values with the smallest possible difference and thus maximize the pairings.
For example:
list1=[20,30,50]
list2=[60,40,25]
iter1 = iter(sorted(list1)) # iterator to run through sorted list1
n1 = next(iter1,None) # n1 is current number in list1
count = 0 # count of paired elements (n1>n2)
for n2 in sorted(list2): # go through sorted list 2
while n1 is not None and n1 <= n2: # skip over ineligible items of list1
n1 = next(iter1,None)
if n1 is None: break # stop when list 1 is exhausted
count += 1 # count 1 pair and move on to next of list2
print(count) # 2
Upvotes: 1