Given an array position[] consisting of N integers where position[i] denotes the position of the ith element, the task is to find the minimum cost required to move all the elements to the same position by performing either of the following two operations:
- Move from position[i] to position[i] + 2 or position[i] – 2. Cost = 0.
- Move from position[i] to position[i] + 1 or position[i] – 1. Cost = 1.
Examples:
Input: position[] = {1, 2, 3}
Output: 1
Explanation:
Operation 1: Move the element at position 3 to position 1. Cost = 0.
Operation 2: Move the element at position 2 to position 1. Cost = 1.
Therefore, total cost = 1.Input: position[] = {2, 2, 2, 3, 3}
Output: 2
Explanation: Move the two elements at position 3 to position 2. Cost of each operation = 1. Therefore, total cost = 2.
Approach: The idea is to traverse the array and count the number of odd and even elements. For each operation involving increment or decrement by two indices, the cost will always be 0. The cost changes only on moving an element from odd to even position or vice-versa. Therefore, the minimum cost required is the minimum of the count of odd and even elements present in the array position[].
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <iostream>using namespace std;// Function to find the minimum// cost required to place all// elements in the same positionint minCost(int arr[], int arr_size){ // Stores the count of even // and odd elements int odd = 0, even = 0; // Traverse the array arr[] for(int i = 0; i < arr_size; i++) { // Count even elements if (arr[i] % 2 == 0) even++; // Count odd elements else odd++; } // Print the minimum count cout << min(even, odd);}// Driver Codeint main(){ // Given array int arr[] = { 1, 2, 3 }; int arr_size = sizeof(arr) / sizeof(arr[0]); // Function Call minCost(arr, arr_size);}// This code is contributed by khushboogoyal499 |
Java
// Java program to implement// the above approachimport java.io.*;class GFG { // Function to find the minimum // cost required to place all // elements in the same position public void minCost(int[] arr) { // Stores the count of even // and odd elements int odd = 0, even = 0; // Traverse the array arr[] for (int i = 0; i < arr.length; i++) { // Count even elements if (arr[i] % 2 == 0) even++; // Count odd elements else odd++; } // Print the minimum count System.out.print( Math.min(even, odd)); } // Driver Code public static void main(String[] args) { GFG obj = new GFG(); // Given array int arr[] = { 1, 2, 3 }; // Function Call obj.minCost(arr); }} |
Python3
# Python3 program to implement# the above approach# Function to find the minimum# cost required to place all# elements in the same positiondef minCost(arr): # Stores the count of even # and odd elements odd = 0 even = 0 # Traverse the array arr[] for i in range(len(arr)): # Count even elements if (arr[i] % 2 == 0): even += 1 # Count odd elements else: odd += 1 # Print the minimum count print(min(even, odd))# Driver Codeif __name__ == '__main__': # Given array arr = [ 1, 2, 3 ] # Function Call minCost(arr)# This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approach using System; class GFG{ // Function to find the minimum// cost required to place all// elements in the same positionpublic void minCost(int[] arr){ // Stores the count of even // and odd elements int odd = 0, even = 0; // Traverse the array arr[] for(int i = 0; i < arr.Length; i++) { // Count even elements if (arr[i] % 2 == 0) even++; // Count odd elements else odd++; } // Print the minimum count Console.Write(Math.Min(even, odd));}// Driver Codepublic static void Main(){ GFG obj = new GFG(); // Given array int[] arr = { 1, 2, 3 }; // Function Call obj.minCost(arr);}}// This code is contributed by sanjoy_62 |
Javascript
<script>// JavaScript program to implement// the above approach // Function to find the minimum // cost required to place all // elements in the same position function minCost(arr) { // Stores the count of even // and odd elements let odd = 0, even = 0; // Traverse the array arr[] for (let i = 0; i < arr.length; i++) { // Count even elements if (arr[i] % 2 == 0) even++; // Count odd elements else odd++; } // Print the minimum count document.write( Math.min(even, odd)); }// Driver code // Given array let arr = [ 1, 2, 3 ]; // Function Call minCost(arr);// This code is contributed by susmitakundugoaldanga.</script> |
1
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
