# Minimum operations required to make all elements in an array of first N odd numbers equal

Minimum operations required to make all elements in an array of first N odd numbers equalGiven an array consisting of first N odd numbers, the task is to find the minimum number of operations required to make all the array elements equal by repeatedly selecting a pair and incrementing one element and decrementing the other element in the pair by 1.Examples:Input: N = 3Output: 2Explanation:Initially, the array is {1, 3, 5}. Following operations are performed:Operation 1: Decrement arr[2] by 1 and increment arr[0] by 1. The array modifies to {2, 3, 4}.Operation 2: Decrement arr[2] by 1 and increment arr[0] by 1. The array modifies to {3, 3, 3}.Therefore, the minimum number of operations required is 2.Input: N = 6Output: 9Naive Approach: The given problem can be solved based on the following observations:It can be observed that making all the array elements equal to the middle element of the array requires minimum number of operations.Therefore, the idea is to traverse the array using a variable i and select the element at index i and (N – i – 1) in each operation and make them equal to the middle element.Follow the steps below to solve the problem:Initialize a variable, say mid, that stores the middle element of the array.Initialize an array arr[] that stores the array element as arr[i] = 2 * i + 1.Find the sum of the array arr[] and store it in a variable say sum.If N is odd, then update the value of mid to arr[N / 2]. Otherwise, update the value of mid to sum / N.Initialize a variable, say ans as 0 that stores the minimum number of operations.Traverse the given array over the range [0, N/2] and increment the value of ans by the value (mid – arr[i]).After completing the above steps, print the value of ans as the result.Below is the implementation of the above approach:Java class GFG { public static int minOperations(int N) { int[] arr = new int[N]; int sum = 0; for (int i = 0; i < N; i++) { arr[i] = (2 * i) + 1; sum = sum + arr[i]; } int mid = 0; if (N % 2 == 0) { mid = sum / N; } else { mid = arr[N / 2]; } int ans = 0; for (int i = 0; i < N / 2; i++) { ans += mid - arr[i]; } return ans; } public static void main(String[] args) { int N = 6; System.out.println( minOperations(N)); }}Time Complexity: O(N)Auxiliary Space: O(N)Efficient Approach: The above approach can be optimized based on the following observation:Therefore, if the value of N is even, then print the value of (N / 2)2. Otherwise, print the value of K * (K + 1) / 2, where K = ((N – 1) / 2) as the resultant operation.Below is the implementation of the above approach:Java class GFG { public static int minOperation(int N) { if (N % 2 == 0) { return (N / 2) * (N / 2); } int k = (N - 1) / 2; return k * (k + 1); } public static void main(String[] args) { int N = 6; System.out.println( minOperation(N)); }}Time Complexity: O(1)Auxiliary Space: O(1)Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer Complete Interview Preparation Course.