I can't think of a solution with this question about 2 arrays:
- Given 2 arrays A and B have the same size (let's say N)
- Each array can swap 2 elements maximum once to satisfy: A[i] <= B[i] with 0<=i<N
- Print "Yes", "No" if there is a solution
Example:
1: Yes
7 5 3 2
5 4 8 7
->
(3) 5 (7) 2
5 (7) 8 (4)
Here is something i tried to do:
def swapPositions(list, pos1, pos2):
list[pos1], list[pos2] = list[pos2], list[pos1]
return list
def isSatisfy(n, a, b):
#add wrong positions
pos = []
for i in range(0,n):
if (a[i] > b[i]):
pos.append(i)
if (len(pos) > 2):
return False
if (len(pos) == 0):
return True
elif (len(pos) == 1):
#try swap in a first
for i in range(0, n):
if (i == pos[0]): continue
if (a[i] >= b[pos[0]] and a[pos[0]] >= b[i]):
return True
#fail
#swap min to wrong pos in a
min = -1
for i in range(0,n):
if (i == pos[0]): continue
if (a[i] <= a[pos[0]] and a[pos[0]] <= b[i]):
min = i
if (i!=-1): swapPositions(a,pos[0],min)
#swap in b
for i in range(0, n):
if (i == pos[0]): continue
if (b[i] >= a[pos[0]] and b[pos[0]] >= a[i]):
return True
return False
elif (len(pos) == 2):
#swap once each array
d1 = 99
min1 = -1
for i in range(0,n):
if (i==pos[0] or i==pos[1]): continue
if (a[i]<=b[pos[0]] and a[pos[0]]<=b[i]):
if (d1 > abs(a[i]-b[i])):
min1 = i
d1 = abs(a[i]-b[i])
if (min1 == -1):
return False
swapPositions(a, pos[0], min1)
for i in range(0,n):
if (i==pos[1]): continue
if (b[i] >= a[pos[1]] and b[pos[1]] >= a[i]):
return True
return False