Given an array arr[] of size N, the task is to make all the array elements odd by choosing an odd length subarray of arr[] and increment all odd positioned elements by 1 in this subarray. Print the count of such operations required.
Examples:
Input: arr[] = {2, 3, 4, 3, 5, 3, 2}
Output: 2
Explanation:
In first operation, choose the subarray {2, 3, 4} and increment all its elements at odd positions, i.e., 1 and 3 of this subarray. The updated array is {3, 3, 5, 3, 5, 3, 2}.
In second operation, choose the last index which is subarray of length 1 and increment its value. The updated array is {3, 3, 5, 3, 5, 3, 3}Input: arr[] = {1, 5, 7}
Output: 0
Explanation: Since all array elements are odd, no changes required.
Approach: The idea is based on the observation that whenever a subarray is chosen, either the odd positioned values are changed or the even positioned values in the original array. The problem can be solved by choosing the subarray greedily in each operation. First, iterate over all the odd indices and mark the starting of the subarray as soon as an even value is found, and end the subarray when an odd value is found, simultaneously updating the number of operations. Repeat the same process for even indices. Follow the steps below to solve the problem:
- Initialize a variable, say flips, to store the minimum number of operations required.
- Traverse even indices of the array arr[] perform the following steps:
- If the current element is odd, then continue iterating.
- Otherwise, iterate every 2nd element starting from that index, until an even element is encountered. After complete traversal of the array or if an even element is encountered, increment flips by 1.
- Repeat step 2 for odd indices also.
- After completing the above steps, print the value of flips as the minimum number of operations as required.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count minimum subarrays// whose odd-indexed elements need to// be incremented to make array oddvoid minOperations(int arr[], int n){ // Stores the minimum number of // operations required int flips = 0; // Iterate over even-indices for (int i = 0; i < n; i += 2) { // Check if the current // element is odd if (arr[i] % 2 == 1) { // If true, continue continue; } // Otherwise, mark the starting // of the subarray and iterate // until i < n and arr[i] is even while (i < n && arr[i] % 2 == 0) { i += 2; } // Increment number of operations flips++; } // Iterate over odd indexed // positions of arr[] for (int i = 1; i < n; i += 2) { // Check if the current // element is odd if (arr[i] % 2 == 1) { // If true, continue continue; } // Otherwise, mark the starting // of the subarray and iterate // until i < n and arr[i] is even while (i < n && arr[i] % 2 == 0) { i += 2; } // Increment the number // of operations flips++; } // Print the number of operations cout << flips;}// Driver Codeint main(){ int arr[] = { 2, 3, 4, 3, 5, 3, 2 }; int N = sizeof(arr) / sizeof(int); // Function Call minOperations(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to count minimum subarrays// whose odd-indexed elements need to// be incremented to make array oddstatic void minOperations(int arr[], int n){ // Stores the minimum number of // operations required int flips = 0; // Iterate over even-indices for(int i = 0; i < n; i += 2) { // Check if the current // element is odd if (arr[i] % 2 == 1) { // If true, continue continue; } // Otherwise, mark the starting // of the subarray and iterate // until i < n and arr[i] is even while (i < n && arr[i] % 2 == 0) { i += 2; } // Increment number of operations flips++; } // Iterate over odd indexed // positions of arr[] for(int i = 1; i < n; i += 2) { // Check if the current // element is odd if (arr[i] % 2 == 1) { // If true, continue continue; } // Otherwise, mark the starting // of the subarray and iterate // until i < n and arr[i] is even while (i < n && arr[i] % 2 == 0) { i += 2; } // Increment the number // of operations flips++; } // Print the number of operations System.out.println(flips);}// Driver Codepublic static void main(String[] args){ int arr[] = { 2, 3, 4, 3, 5, 3, 2 }; int N = arr.length; // Function Call minOperations(arr, N);}}// This code is contributed by jana_sayantan |
C#
// C# program for the above approachusing System;class GFG{ // Function to count minimum subarrays// whose odd-indexed elements need to// be incremented to make array oddstatic void minOperations(int []arr, int n){ // Stores the minimum number of // operations required int flips = 0; // Iterate over even-indices for(int i = 0; i < n; i += 2) { // Check if the current // element is odd if (arr[i] % 2 == 1) { // If true, continue continue; } // Otherwise, mark the starting // of the subarray and iterate // until i < n and arr[i] is even while (i < n && arr[i] % 2 == 0) { i += 2; } // Increment number of operations flips++; } // Iterate over odd indexed // positions of []arr for(int i = 1; i < n; i += 2) { // Check if the current // element is odd if (arr[i] % 2 == 1) { // If true, continue continue; } // Otherwise, mark the starting // of the subarray and iterate // until i < n and arr[i] is even while (i < n && arr[i] % 2 == 0) { i += 2; } // Increment the number // of operations flips++; } // Print the number of operations Console.WriteLine(flips);}// Driver Codepublic static void Main(String[] args){ int []arr = { 2, 3, 4, 3, 5, 3, 2 }; int N = arr.Length; // Function Call minOperations(arr, N);}}// This code is contributed by Princi Singh |
Python3
# Python3 program for the above approach# Function to count minimum subarrays# whose odd-indexed elements need to# be incremented to make array odddef minOperations(arr, n) : # Stores the minimum number of # operations required flips = 0; i = 0; # Iterate over even-indices while i < n : # Check if the current # element is odd if (arr[i] % 2 == 1) : i += 2; # If true, continue continue; # Otherwise, mark the starting # of the subarray and iterate # until i < n and arr[i] is even while (i < n and arr[i] % 2 == 0) : i += 2; # Increment number of operations flips += 1; i += 2; # Iterate over odd indexed # positions of arr[] i = 1 while i < n : # Check if the current # element is odd if (arr[i] % 2 == 1) : i += 2; # If true, continue continue; # Otherwise, mark the starting # of the subarray and iterate # until i < n and arr[i] is even while (i < n and arr[i] % 2 == 0) : i += 2; # Increment the number # of operations flips += 1; i += 2; # Print the number of operations print(flips);# Driver Codeif __name__ == "__main__" : arr = [ 2, 3, 4, 3, 5, 3, 2 ]; N = len(arr); # Function Call minOperations(arr, N); # This code is contributed by AnkThon |
Javascript
<script>// Javascript program for the above approach// Function to count minimum subarrays// whose odd-indexed elements need to// be incremented to make array oddfunction minOperations(arr, n){ // Stores the minimum number of // operations required let flips = 0; // Iterate over even-indices for(let i = 0; i < n; i += 2) { // Check if the current // element is odd if (arr[i] % 2 == 1) { // If true, continue continue; } // Otherwise, mark the starting // of the subarray and iterate // until i < n and arr[i] is even while (i < n && arr[i] % 2 == 0) { i += 2; } // Increment number of operations flips++; } // Iterate over odd indexed // positions of arr[] for(let i = 1; i < n; i += 2) { // Check if the current // element is odd if (arr[i] % 2 == 1) { // If true, continue continue; } // Otherwise, mark the starting // of the subarray and iterate // until i < n and arr[i] is even while (i < n && arr[i] % 2 == 0) { i += 2; } // Increment the number // of operations flips++; } // Print the number of operations document.write(flips);} // Driver Code let arr = [ 2, 3, 4, 3, 5, 3, 2 ]; let N = arr.length; // Function Call minOperations(arr, N); // This code is contributed by souravghosh0416.</script> |
Output:
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
