Given an array arr[] of length N, the task is to replace all subarrays of only even elements by their length if the length is greater than or equal to K.
Examples:
Input: arr[] = {3, 6, 10, 2, 7, 6, 4, 8}, K = 2
Output: 3 3 7 3
Explanation: There are two subarrays with consecutive even numbers {6, 10, 2} and {6, 4, 8}.
So they are replaced by their length 3 and 3 respectively.Input: arr[] = {4, 8, 3, 6, 8}, K=3
Output: 4 8 3 6 8
Explanation: No subarray exists for which length of consecutive even numbers is greater than or equal to 3.
Approach: Follow the below steps to answer this problem:
- Create two vectors, one to store answer ans and one to store consecutive even numbers temp.
- If (K >= N), then return the original vector arr.
- Now, traverse the array, and for each element:
- If the current element is odd, then check if the length of temp is greater or equal to K.
- If it is, then push its length in ans vector.
- Else push the elements of temp in ans vector.
- Clear the temp vector.
- Push the current element in the ans vector.
- If the current element is even, then push it in temp.
- If the current element is odd, then check if the length of temp is greater or equal to K.
- After the loop ends, vector ans contains the final answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to replace all subarrays of// even elements with their length if their// length is greater than or equal to Kvector<int> processArray(vector<int>& arr, int& K){ int N = arr.size(), i, count = 0; vector<int> ans; vector<int> temp; if (K >= N) return arr; for (i = 0; i < N; i++) { // If arr[i] is odd if (arr[i] & 1) { if (temp.size() >= K) ans.push_back(temp.size()); else { for (auto& x : temp) { ans.push_back(x); } } ans.push_back(arr[i]); temp.clear(); } // If arr[i] is even else { temp.push_back(arr[i]); } } if (temp.size() >= K) { ans.push_back(temp.size()); } else { for (auto& x : temp) { ans.push_back(x); } } return ans;}// Driver Codeint main(){ vector<int> arr = { 3, 6, 10, 2, 7, 6, 4, 8 }; int K = 2; vector<int> ans = processArray(arr, K); for (auto& x : ans) cout << x << " "; return 0;} |
Java
// Java program for the above approachimport java.util.ArrayList;import java.util.Arrays;import java.util.List;class GFG { // Function to replace all subarrays of // even elements with their length if their // length is greater than or equal to K static List<Integer> processArray(List<Integer> arr, int K) { int N = arr.size(); ArrayList<Integer> ans = new ArrayList<Integer>(); ArrayList<Integer> temp = new ArrayList<Integer>(); ; if (K >= N) return arr; for (int i = 0; i < N; i++) { // If arr[i] is odd if ((arr.get(i) & 1) > 0) { if (temp.size() >= K) ans.add(temp.size()); else { for (int x : temp) { ans.add(x); } } ans.add(arr.get(i)); temp.clear(); } // If arr[i] is even else { temp.add(arr.get(i)); } } if (temp.size() >= K) { ans.add(temp.size()); } else { for (int x : temp) { ans.add(x); } } return ans; } // Driver Code public static void main(String args[]) { List<Integer> arr = Arrays.asList(3, 6, 10, 2, 7, 6, 4, 8); int K = 2; List<Integer> ans = processArray(arr, K); for (int x : ans) System.out.print(x + " "); }}// This code is contributed by saurabh_jaiswal. |
Python3
# python3 program for the above approach# Function to replace all subarrays of# even elements with their length if their# length is greater than or equal to Kdef processArray(arr, K): N, count = len(arr), 0 ans = [] temp = [] if (K >= N): return arr for i in range(0, N): # If arr[i] is odd if (arr[i] & 1): if (len(temp) >= K): ans.append(len(temp)) else: for x in temp: ans.append(x) ans.append(arr[i]) temp.clear() # If arr[i] is even else: temp.append(arr[i]) if (len(temp) >= K): ans.append(len(temp)) else: for x in temp: ans.append(x) return ans# Driver Codeif __name__ == "__main__": arr = [3, 6, 10, 2, 7, 6, 4, 8] K = 2 ans = processArray(arr, K) for x in ans: print(x, end=" ") # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG { // Function to replace all subarrays of // even elements with their length if their // length is greater than or equal to K static List<int> processArray(List<int> arr, int K) { int N = arr.Count; List<int> ans = new List<int>(); List<int> temp = new List<int>(); ; if (K >= N) return arr; for (int i = 0; i < N; i++) { // If arr[i] is odd if ((arr[i] & 1) > 0) { if (temp.Count >= K) ans.Add(temp.Count); else { foreach (int x in temp) { ans.Add(x); } } ans.Add(arr[i]); temp.Clear(); } // If arr[i] is even else { temp.Add(arr[i]); } } if (temp.Count >= K) { ans.Add(temp.Count); } else { foreach (int x in temp) { ans.Add(x); } } return ans; } // Driver Code public static void Main(String []args) { List<int> arr = new List<int>(new int[]{3, 6, 10, 2, 7, 6, 4, 8}); int K = 2; List<int> ans = processArray(arr, K); foreach (int x in ans) Console.Write(x + " "); }}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript code for the above approach // Function to replace all subarrays of // even elements with their length if their // length is greater than or equal to K function processArray(arr, K) { let N = arr.length, i, count = 0; let ans = []; let temp = []; if (K >= N) return arr; for (i = 0; i < N; i++) { // If arr[i] is odd if (arr[i] & 1) { if (temp.length >= K) ans.push(temp.length); else { for (let x of temp) { ans.push(x); } } ans.push(arr[i]); temp = []; } // If arr[i] is even else { temp.push(arr[i]); } } if (temp.length >= K) { ans.push(temp.length); } else { for (let x of temp) { ans.push(x); } } return ans; } // Driver Code let arr = [3, 6, 10, 2, 7, 6, 4, 8]; let K = 2; let ans = processArray(arr, K); for (let x of ans) document.write(x + " "); // This code is contributed by Potta Lokesh </script> |
Output
3 3 7 3
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
Share your thoughts in the comments
