CODEWITHSUNDEEP
arraysalgorithmminimization
Clarence Callahan
Clarence Callahan

Reputation: 53

Minimum number of operations to make two arrays equal

Given 2 arrays of integers, A and B, an operation on array B is defined as follows:

B[i] = B[i]+2 and B[j] = B[j]-2, where i != j

The array is considered equal if the frequency of all the elements is same, the array need not be ordered, find the minimum operations required

Input:
 A = [ 2, 10, 14 ]

B = [ 6, 2, 18 ]

Output: 2

Explanation :

1st operation:  select i=0; j=2; 
B[i] += 2 i.e B[0]=8;
B[j] -= 2 i.e B[2] = 16;
B after 1st operation [8,2,16]

2nd operation:  select i=0; j=2; 
B[i] += 2 i.e B[0]=10;
B[j] -= 2 i.e B[2] = 14;
B after 2nd operation [10,2,14]

Order doesnt matter, so we have made the arrays equal return 2;

I am unable get an approach to solve this and couldn't find any similar questions, so posting this here, thanks in advance.

Upvotes: 1

Views: 3685

Answers (2)

Ji Li
Ji Li

Reputation: 1

A = [2, 10, 14]( % 2 == 0)
B = [2, 6, 18]( % 2 == 0)

another example

A = [1, 2, 5] -> [1, 5]( % 2 == 1) & [2]( % 2 == 0)
B = [1, 3, 4] -> [1, 3]( % 2 == 1) & [4]( % 2 == 0)

Notice that (a + k) mod k == a.

Assuming we already have a sorted array.

We divide the array into k parts, according to the mod k value of the element, then we sum all absolute differences, it's four times the answer.

k = 2
A.sort(key=lambda x: x % k)
B.sort(key=lambda x: x % k)
result = 0
n = len(A)
for i in range(n):
    result += abs(A[i] - B[i])
print(result >> 2)
# A = [1, 2, 5]
# B = [1, 3, 4]
# result = 1
# A = [2, 10, 14]
# B = [6, 2, 18]
# result = 2

O(N log N) because of sorting.

Upvotes: 0

Dave
Dave

Reputation: 9085

Assuming the arrays are solvable, then sort the arrays (by parity, and then by value), add up the absolute value of the deltas and divide by 4.

E.g.

A = [ 2, 10, 14 ], already sorted
B = [ 6, 2, 18 ], sorted becomes [2, 6, 18]

Sum of absolute value of deltas = 0 + 4 + 4 = 8. 8/4 = 2 so 2 moves.

Upvotes: 0

Related Questions