Minimum Operations to Make Array Equal 🍋
Learn this problemProblem statement
From an array source of n integers, in a single operation, choose any even-length subarray. Alternately add and subtract 1 from each element of the subarray from left to right. For example, for source = [1, 2, 3, 4, 5, 6] the subarray [3, 4, 5, 6] can be chosen and made [3+1, 4-1, 5+1, 6-1]=[4, 3, 6, 5]. Then source = [1, 2, 4, 3, 6, 5].
Given two arrays source and target of n integers, find the minimum number of operations that must be performed on the array source to make it equal to the array target. Report -1 if it is not possible to make the two arrays equal.
Function
minOperations(source: int[], target: int[]) → int
Complete the function minOperations in the editor.
minOperations has the following parameters:
- 1.
int[] source: an array of integers - 2.
int[] target: an array of integers
Returns
int: the minimum number of operations, or -1 if it's not possible
Examples
Example 1
source = [4, 3, 1, 3]target = [6, 2, 3, 0]return = 4
It is optimal to choose the subarray [3,1] and get source = [4,4,0,3]. Now choose [0,3] to get source = [4,4,1,2]. Now choose the entire array to get source = [5,3,2,1]. Finally choose [5,1] to get source = [6,2,3,0]. Thus the two arrays can be equalized in at most 4 operations. Hence the operation is 4.
Constraints
1 <= n <= 10^5-10^9 <= source[i], target[i] <= 10^9