Minimum operations required to make all elements in an array of first N odd numbers equal
Given 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 = 3
Output: 2
Explanation:
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 = 6
Output: 9
Naive 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:
C++14
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum number // of operations required to make the // array elements equal int minOperations( int N) { // Stores the array elements int arr[N]; // Stores the sum of the array int sum = 0; // Iterate over the range [0, N] for ( int i = 0; i < N; i++) { // Update the value arr[i] arr[i] = (2 * i) + 1; // Increment the sum by // the value arr[i] sum = sum + arr[i]; } // Stores the middle element int mid = 0; // If N is even if (N % 2 == 0) { mid = sum / N; } // Otherwise else { mid = arr[N / 2]; } // Stores the result int ans = 0; // Traverse the range [0, N / 2] for ( int i = 0; i < N / 2; i++) { // Update the value of ans ans += mid - arr[i]; } // Return the result return ans; } // Driver Code int main() { int N = 6; cout << minOperations(N); return 0; } // This code is contributed by susmitakundugoaldanga |
Java
// Java program for the above approach class GFG { // Function to find the minimum number // of operations required to make the // array elements equal public static int minOperations( int N) { // Stores the array elements int [] arr = new int [N]; // Stores the sum of the array int sum = 0 ; // Iterate over the range [0, N] for ( int i = 0 ; i < N; i++) { // Update the value arr[i] arr[i] = ( 2 * i) + 1 ; // Increment the sum by // the value arr[i] sum = sum + arr[i]; } // Stores the middle element int mid = 0 ; // If N is even if (N % 2 == 0 ) { mid = sum / N; } // Otherwise else { mid = arr[N / 2 ]; } // Stores the result int ans = 0 ; // Traverse the range [0, N / 2] for ( int i = 0 ; i < N / 2 ; i++) { // Update the value of ans ans += mid - arr[i]; } // Return the result return ans; } // Driver Code public static void main(String[] args) { int N = 6 ; System.out.println( minOperations(N)); } } |
Python3
# Python3 program for the above approach # Function to find the minimum number # of operations required to make the # array elements equal def minOperations(N): # Stores the array elements arr = [ 0 ] * N # Stores the sum of the array sum = 0 # Iterate over the range [0, N] for i in range (N) : # Update the value arr[i] arr[i] = ( 2 * i) + 1 # Increment the sum by # the value arr[i] sum = sum + arr[i] # Stores the middle element mid = 0 # If N is even if N % 2 = = 0 : mid = sum / N # Otherwise else : mid = arr[ int (N / 2 )] # Stores the result ans = 0 # Traverse the range [0, N / 2] for i in range ( int (N / 2 )): # Update the value of ans ans + = mid - arr[i] # Return the result return int (ans) # Driver Code N = 6 print (minOperations(N)) # This code is contributed by Dharanendra L V. |
C#
// C# program for the above approach using System; class GFG{ // Function to find the minimum number // of operations required to make the // array elements equal public static int minOperations( int N) { // Stores the array elements int [] arr = new int [N]; // Stores the sum of the array int sum = 0; // Iterate over the range [0, N] for ( int i = 0; i < N; i++) { // Update the value arr[i] arr[i] = (2 * i) + 1; // Increment the sum by // the value arr[i] sum = sum + arr[i]; } // Stores the middle element int mid = 0; // If N is even if (N % 2 == 0) { mid = sum / N; } // Otherwise else { mid = arr[N / 2]; } // Stores the result int ans = 0; // Traverse the range [0, N / 2] for ( int i = 0; i < N / 2; i++) { // Update the value of ans ans += mid - arr[i]; } // Return the result return ans; } // Driver Code public static void Main( string [] args) { int N = 6; Console.WriteLine(minOperations(N)); } } // This code is contributed by ukasp |
Javascript
<script> // javascript program for the above approach // Function to find the minimum number // of operations required to make the // array elements equal function minOperations(N) { // Stores the array elements let arr = Array.from({length: N}, (_, i) => 0); // Stores the sum of the array let sum = 0; // Iterate over the range [0, N] for (let i = 0; i < N; i++) { // Update the value arr[i] arr[i] = (2 * i) + 1; // Increment the sum by // the value arr[i] sum = sum + arr[i]; } // Stores the middle element let mid = 0; // If N is even if (N % 2 == 0) { mid = sum / N; } // Otherwise else { mid = arr[N / 2]; } // Stores the result let ans = 0; // Traverse the range [0, N / 2] for (let i = 0; i < N / 2; i++) { // Update the value of ans ans += mid - arr[i]; } // Return the result return ans; } // Driver Code let N = 6; document.write(minOperations(N)); </script> |
9
Time Complexity: O(N)
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized based on the following observation:
- If N is odd then the result is the sum of first N / 2 even numbers i.e., (K * (K + 1)) / 2, where K = (N / 2).
- Otherwise, the result is the sum of the first K odd numbers i.e., K * K, where K = ((N – 1) / 2).
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:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum number // of operations required to make the // array elements equal int minOperation( int N) { // If the value of N is even if (N % 2 == 0) { // Return the value return (N / 2) * (N / 2); } // Otherwise, N is odd int k = (N - 1) / 2; // Return the value return k * (k + 1); } // Driver Code int main() { int N = 6; cout << minOperation(N); return 0; } // This code is contributed by code_hunt. |
Java
// Java program for the above approach class GFG { // Function to find the minimum number // of operations required to make the // array elements equal public static int minOperation( int N) { // If the value of N is even if (N % 2 == 0 ) { // Return the value return (N / 2 ) * (N / 2 ); } // Otherwise, N is odd int k = (N - 1 ) / 2 ; // Return the value return k * (k + 1 ); } // Driver Code public static void main(String[] args) { int N = 6 ; System.out.println( minOperation(N)); } } |
C#
// C# program for the above approach using System; class GFG{ // Function to find the minimum number // of operations required to make the // array elements equal public static int minOperation( int N) { // If the value of N is even if (N % 2 == 0) { // Return the value return (N / 2) * (N / 2); } // Otherwise, N is odd int k = (N - 1) / 2; // Return the value return k * (k + 1); } // Driver code static void Main() { int N = 6; Console.WriteLine(minOperation(N)); } } // This code is contributed by abhinavjain194 |
Python3
# Python3 program for the above approach # Function to find the minimum number # of operations required to make the # array elements equal def minOperation(N) : # If the value of N is even if (N % 2 = = 0 ) : # Return the value return (N / 2 ) * (N / 2 ) # Otherwise, N is odd k = (N - 1 ) / 2 # Return the value return (k * (k + 1 )) # Driver Code N = 6 print ( int (minOperation(N))) # This code is contributed by souravghosh0416. |
Javascript
<script> // Javascript program implementation // of the approach // Function to find the minimum number // of operations required to make the // array elements equal function minOperation(N) { // If the value of N is even if (N % 2 == 0) { // Return the value return (N / 2) * (N / 2); } // Otherwise, N is odd let k = (N - 1) / 2; // Return the value return k * (k + 1); } // Driver Code let N = 6; document.write( minOperation(N)); // This code is contributed by splevel62. </script> |
9
Time Complexity: O(1)
Auxiliary Space: O(1)
Contact Us