Count of product operations to make adjacent Array elements of different parity
Given an array arr[] consisting of N elements. At each operation, you can select any 2 adjacent elements in which both the elements are of the same parity and then delete both of them, and insert their product in the same position, the task is to find the minimum number of operations needed for this.
Examples:
Input : arr[] = {3, 5, 7, 8, 9}
Output : Minimum Operation = 2
Explanation : first we will select first 2 indices with value 3 and 5 then our new array will become {15, 7, 8, 9}and then again we will select first 2 indices and new array will be {105, 8, 9} Hence, After 2 operations every adjacent element of our array will be of different parity.Input : arr[] = {1, 4, 7, 10}
Output : Minimum Operation = 0
Explanation : Each adjacent pair is of different parity.
Approach: To solve the problem follow the below observations:
Observations:
We know that,
- Even * Even = Even
- Odd * Odd = Odd
- Odd * Even = Even
Now, If we took a closer look at each operation as well problem statement we will find that if adjacent elements are both even or both odd then we will increase our count by one. Because if they are already of different parity we don’t have to change otherwise their product will be of the same parity.
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function for finding min operation int minOp( int arr[], int n) { int minOperation = 0; for ( int i = 0; i < n - 1; i++) { // Checking weather parity is // same or different if ((arr[i] % 2 == arr[i + 1] % 2)) { minOperation++; } } return minOperation; } // Driver function int main() { int arr[] = { 5, 6, 2, 4, 3 }; int n = sizeof (arr) / sizeof (arr[0]); // Function Call cout << "Minimum Operation = " << minOp(arr, n); return 0; } |
Java
// Java code for the above approach: import java.util.*; class GFG { // Function for finding min operation public static int minOp( int arr[], int n) { int minOperation = 0 ; for ( int i = 0 ; i < n - 1 ; i++) { // Checking weather parity is // same or different if ((arr[i] % 2 == arr[i + 1 ] % 2 )) { minOperation++; } } return minOperation; } // Driver function public static void main(String[] args) { int arr[] = { 5 , 6 , 2 , 4 , 3 }; int n = arr.length; // Function Call System.out.println( "Minimum Operation = " + minOp(arr, n)); } } // This Code is Contributed by Prasad Kandekar(prasad264) |
Python3
# Python code for the above approach: # Function for finding min operation def minOp(arr): n = len (arr) minOperation = 0 for i in range (n - 1 ): # Checking weather parity is # same or different if arr[i] % 2 = = arr[i + 1 ] % 2 : minOperation + = 1 return minOperation # Driver function if __name__ = = '__main__' : arr = [ 5 , 6 , 2 , 4 , 3 ] n = len (arr) # Function Call print ( "Minimum Operation =" , minOp(arr)) # This Code is Contributed by rutikbhosale |
C#
// C# code for the above approach: using System; class GFG { public static int minOp( int [] arr, int n) { int minOperation = 0; for ( int i = 0; i < n - 1; i++) { if ((arr[i] % 2 == arr[i + 1] % 2)) { minOperation++; } } return minOperation; } public static void Main ( string [] args) { int [] arr = { 5, 6, 2, 4, 3 }; int n = arr.Length; // Function Call Console.WriteLine( "Minimum Operation = " + minOp(arr, n)); } } |
Javascript
// Javascript code for the above approach // Function for finding min operation function minOp(arr) { let minOperation = 0; for (let i = 0; i < arr.length - 1; i++) { // Checking weather parity is same or different if (arr[i] % 2 === arr[i + 1] % 2) { minOperation++; } } return minOperation; } // Driver function function main() { const arr = [5, 6, 2, 4, 3]; const n = arr.length; // Function Call console.log( "Minimum Operation = " + minOp(arr)); } // Invoke the driver function main(); |
Minimum Operation = 2
Time Complexity: O(N), where N represents the size of the given array.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Method #2:Using Bitwise Operators
- Initialize a variable ‘min_ops’ to 0 to count the number of operations.
- Iterate through the array from the first element to the second last element.
- Check if the parity of the current element and the next element is the same.
- If the parity is the same, multiply the larger element by 2 to make them have different parity.
- Increment the ‘min_ops’ variable by 1.
- Continue iterating till the end of the array.
- Return the ‘min_ops’ variable.
C++
// C++ code #include <iostream> #include <vector> using namespace std; // Function to find the minimum number of product operations int min_operations(vector< int >& arr) { int n = arr.size(); int min_ops = 0; for ( int i = 0; i < n-1; i++) { // Check if the parity of the adjacent elements is the same if (((arr[i] ^ arr[i+1]) & 1) == 0) { // Perform the product operation if (arr[i] < arr[i+1]) { arr[i+1] *= 2; } else { arr[i] *= 2; } min_ops += 1; } } return min_ops; } // Driver code int main() { vector< int > arr = {5, 6, 2, 4, 3}; cout << "Minimum number of product operations: " << min_operations(arr) << endl; return 0; } // This Code is Contributed by Utkarsh Kumar |
Java
import java.util.ArrayList; import java.util.List; public class GFG { // Function to find the minimum number of product operations public static int minOperations(List<Integer> arr) { int n = arr.size(); int minOps = 0 ; for ( int i = 0 ; i < n - 1 ; i++) { // Check if the parity of the adjacent elements is the same if (((arr.get(i) ^ arr.get(i + 1 )) & 1 ) == 0 ) { // Perform the product operation if (arr.get(i) < arr.get(i + 1 )) { arr.set(i + 1 , arr.get(i + 1 ) * 2 ); } else { arr.set(i, arr.get(i) * 2 ); } minOps += 1 ; } } return minOps; } // Driver code public static void main(String[] args) { List<Integer> arr = new ArrayList<>(); arr.add( 5 ); arr.add( 6 ); arr.add( 2 ); arr.add( 4 ); arr.add( 3 ); System.out.println( "Minimum number of product operations: " + minOperations(arr)); } } |
Python3
# Function to find the minimum number of product operations def min_operations(arr): n = len (arr) min_ops = 0 for i in range (n - 1 ): # Check if the parity of the adjacent elements is the same if (arr[i] ^ arr[i + 1 ]) & 1 = = 0 : # Perform the product operation if arr[i] < arr[i + 1 ]: arr[i + 1 ] * = 2 else : arr[i] * = 2 min_ops + = 1 return min_ops # Driver code arr = [ 5 , 6 , 2 , 4 , 3 ] print ( "Minimum number of product operations:" , min_operations(arr)) |
C#
// C# Code using System; using System.Collections.Generic; public class GFG { // Function to find the minimum number of product // operations static int MinOperations(List< int > arr) { int n = arr.Count; int minOps = 0; for ( int i = 0; i < n - 1; i++) { // Check if the parity of the adjacent elements // is the same if (((arr[i] ^ arr[i + 1]) & 1) == 0) { // Perform the product operation if (arr[i] < arr[i + 1]) { arr[i + 1] *= 2; } else { arr[i] *= 2; } minOps += 1; } } return minOps; } // Driver code static public void Main() { List< int > arr = new List< int >{ 5, 6, 2, 4, 3 }; Console.WriteLine( "Minimum number of product operations: " + MinOperations(arr)); } } |
Javascript
// JavaScript code for above approach // Function to find the minimum number of product operations function minOperations(arr) { const n = arr.length; let minOps = 0; for (let i = 0; i < n - 1; i++) { // Check if the parity of the adjacent elements is the same if ((arr[i] ^ arr[i + 1]) % 2 === 0) { // Perform the product operation if (arr[i] < arr[i + 1]) { arr[i + 1] *= 2; } else { arr[i] *= 2; } minOps += 1; } } return minOps; } // Driver code const arr = [5, 6, 2, 4, 3]; console.log( "Minimum number of product operations: " + minOperations(arr)); // This code is contributed by prasad264 |
Minimum number of product operations: 2
Time Complexity: O(N), where N represents the size of the given array.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Contact Us