Introduction
In this article, we'll look at how to find the smallest number of moves to equalize array elements. We'll compare elements from two arrays to see if they're equal. Both arrays must have the same number of elements as a pre-condition, i.e., both arrays must be the same length.
Also See, Array Implementation of Queue and Rabin Karp Algorithm
Problem Statement
We need to transform the first array into the second array with the fewest possible operations given two identical arrays. We can either increase or decrease the value of an element by one in a function. It's worth noting that the sequence in which elements appear does not have to match.
We can add or subtract 1 from any number to convert it to another.
Sample Examples
Example 1:
Input:
A= { 5, 3, 3 }, B= { 3, 4, 4 }
Output:
2
Explanation: We can turn any 3 into a 4 with a single operation and 3 into 4 with a single decrement operation. As a result, A[] becomes (4, 4, 3) a permutation of B[].
Example 2
Input :
P= { 1, 1, 3}, Q= { 2, 2, 1 }
Output :
2
Explanation: We can convert any 1 to 2 with a single operation, and 3 to 2 with a single decrement operation. As a result, P[] becomes 2, 2, 1 (a permutation of P[]).
Approach
We will use Equalising the elements of the Array as an efficient approach for the problem of making elements of two arrays identical with minimum increment or decrement.
Algorithm
-
Both arrays are sorted in ascending order.
-
Save the final result as a variable.
-
After sorting both arrays, each array is now in ascending order. As a result, we'll now compare each array element and increment or decrement the value of array b[] depending on the value.
The implementation of the above strategy is shown below.
Implementation
// operations to make array elements same.
#include <bits/stdc++.h>
using namespace std;
int MinimumOpera(int p[], int q[], int m)
{
//Both arrays are sorted in ascending order
sort(p, p + m);
sort(q, q + m);
// to save the final result as a variable
int result = 0;
// Following the sorting of both arrays,
//Each array is now in ascending order.
//As a result, we'll now compare each
//element of the array and increment or decrement
//the value of array b[] depending on the value.
for (int i = 0; i < m; ++i) {
result = result + abs(p[i] - q[i]);
}
return result;
}
// Driver code
int main()
{
int p[] = { 3, 1, 1 };
int q[] = { 1, 2, 2 };
int m = sizeof(p) / sizeof(p[0]);
cout << MinimumOpera(p, q, m);
return 0;
}
Output:
2
Complexities
Time Complexity
Here in the implementation, we are using the sorting algorithm which has time complexity O(n log n). So, the overall time complexity of our algorithm is O(n log n). Where n is the no of elements in the given array.
Space Complexity
The space complexity of our algorithm is O(1). Since we are not using any extra space.