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.