Minimize moves required to make array elements equal by incrementing and decrementing pairs | Set 2

Given an array arr[] of size N, the task is to print the minimum number of moves required to make all array elements equal by selecting any pair of distinct indices and then increment the element at the first index and decrement the element at the other index by 1 each time. If it is impossible to make all array elements equal, then print “-1“.Examples: Input: arr[] = {5, 4, 1, 10}Output: 5Explanation:  One of the possible ways to perform operations is:Operation 1: Select the indices 1 and 3 and then increment arr[1] by 1 and decrement arr[3] by 1. Thereafter, the array modifies to {5, 5, 1, 9}.Operation 2: Select the indices 2 and 3 and then increment arr[2] by 1 and decrement arr[3] by 1. Thereafter, the array modifies to {5, 5, 2, 8}.Operation 3: Select the indices 2 and 3 and then increment arr[2] by 1 and decrement arr[3] by 1. Thereafter, the array modifies to {5, 5, 3, 7}.Operation 4: Select the indices 2 and 3 and then increment arr[2] by 1 and decrement arr[3] by 1. Thereafter, the array modifies to {5, 5, 4, 6}.Operation 5: Select the indices 2 and 3 and then increment arr[2] by 1 and decrement arr[3] by 1. Thereafter, the array modifies to {5, 5, 5, 5}.Therefore, the total number of moves needed is 5. Also, it is the minimum possible moves needed.Input: arr[] = {1, 4}Output: -1Naive Approach: Refer to the previous post for the simplest approach to solve the problem.Time Complexity: O(NlogN)Auxiliary Space: O(1)Efficient Approach: The above approach can be optimized based on the following observations: It can be observed that in each operation, the sum of the array remains the same. Therefore, if the sum of the array is not divisible N, then it is impossible to make all the array elements equal.Otherwise, each array element will be equal to the sum of the array divided by N, say k.Therefore, the idea is to iterate over the array and find the absolute difference between the current element and k and add to ans.Since in each operation, both increments and decrements are performed together, ans / 2 is the number of operations required.Follow the steps below to solve the problem:Initialize a variable, say ans as 0, to store the count of the operations required.Find the sum of the array and store it in a variable, say sum.Now, if the sum is not divisible by N, then print “-1“. Otherwise, store k = sum / N.Initialize variables, say i = 0, and traverse the array.Iterate while i is less than N and add the absolute difference between the current element and k to ans:Finally, after completing the above steps, print ans / 2.Below is the implementation of the above approach:Python3def find(arr, N):        Sum = sum(arr)        if Sum % N:        return -1    else:               k = Sum // N                        ans = 0        i = 0                        while i < N:                                                ans = ans + abs(k-arr[i])                        i += 1                return ans // 2if __name__ == '__main__':        arr = [5, 4, 1, 10]    N = len(arr)        print(find(arr, N))Javascriptfunction find(arr, N){             let Sum = 0;    let i = 0;    let ans = 0;         for(i = 0; i < N; i++)    {        Sum += arr[i];    }        if (Sum % N)    {        return -1;    }    else    {                         k = Math.floor(Sum / N);                        ans = 0;        i = 0;                        while (i < N)        {                                                             ans = ans + Math.abs(k - arr[i]);                        i += 1;        }    }             return Math.floor(ans / 2);}let arr = [ 5, 4, 1, 10 ]let N = arr.length;document.write(find(arr, N));Output: 5Time Complexity: O(N)Auxiliary Space: O(1)Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.