Given an array arr[]. The task is to find the length of the longest subarray of arr[] such that it contains only even elements.
Examples:
Input : arr[] = { 5, 2, 4, 7 }
Output : Length = 2
subArr[] = {2, 4}
Input : arr[] = {9, 8, 5, 4, 4, 4, 2, 4, 1}
Output : Length 5
subArr[] = {4, 4, 4, 2, 4}
Naive Approach
The idea is to find all subarrays and then pick those subarrays whose all elements are even. Then find the length of the longest subarray from those subarrays.
Steps to implement-
- Declare a variable ans to store the final answer
- Run two nested loops to find all subarrays
- Check whether any subarray contains all even elements
- If any subarray contains all even elements
- Then update ans with the maximum of ans and its length
Code-
C++
// C++ Program to find the Length of the// largest Subarray with only even elements#include <bits/stdc++.h>using namespace std;// Function to find the Length of the// largest Subarray with only even elementsint maxEvenSubarray(int arr[], int N){ //To store final answer int ans=0; //Find all Subarray for(int i=0;i<N;i++){ //To store length of subarray int length=0; for(int j=i;j<N;j++){ //Increment the length length++; //Boolean varibale to tell whether subarray //contains all even elements bool val=false; int k=i; while(k<=j){ if(arr[k]%2==1){break;} k++; } //Check whether all elements of a subarray //are even if(k==j+1){val=true;} //When all elements of a subarray are even if(val==true){ ans=max(ans,length); } } } return ans;}// Driver Codeint main(){ int arr[] = { 9, 8, 5, 4, 4, 4, 2, 4, 1 }; int N = sizeof(arr) / sizeof(arr[0]); cout << maxEvenSubarray(arr, N); return 0;} |
Java
// Java Program to find the Length of the// largest Subarray with only even elementsimport java.util.Scanner;public class GFG { // Function to find the Length of the // largest Subarray with only even elements static int maxEvenSubarray(int arr[], int N) { // To store the final answer int ans = 0; // Find all Subarrays for (int i = 0; i < N; i++) { // To store the length of the subarray int length = 0; for (int j = i; j < N; j++) { // Increment the length length++; // Boolean variable to tell whether subarray // contains all even elements boolean val = false; int k = i; while (k <= j) { if (arr[k] % 2 == 1) { break; } k++; } // Check whether all elements of a subarray // are even if (k == j + 1) { val = true; } // When all elements of a subarray are even if (val) { ans = Math.max(ans, length); } } } return ans; } // Driver Code public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // Input array int arr[] = { 9, 8, 5, 4, 4, 4, 2, 4, 1 }; int N = arr.length; System.out.println(maxEvenSubarray(arr, N)); }} |
Python3
# Python Program to find the Length of the# largest Subarray with only even elementsdef max_even_subarray(arr): # To store the final answer ans = 0 # Find all subarrays for i in range(len(arr)): # To store the length of the subarray length = 0 for j in range(i, len(arr)): # Increment the length length += 1 # Boolean variable to tell whether subarray # contains all even elements val = False k = i while k <= j: if arr[k] % 2 == 1: break k += 1 # Check whether all elements of a subarray are even if k == j + 1: val = True # When all elements of a subarray are even if val == True: ans = max(ans, length) return ans# Driver codearr = [9, 8, 5, 4, 4, 4, 2, 4, 1]print(max_even_subarray(arr)) |
C#
using System;class Program { // Function to find the Length of the largest Subarray // with only even elements static int MaxEvenSubarray(int[] arr, int N) { // To store final answer int ans = 0; // Find all Subarrays for (int i = 0; i < N; i++) { // To store the length of subarray int length = 0; for (int j = i; j < N; j++) { // Increment the length length++; // Boolean variable to tell whether subarray // contains all even elements bool val = false; int k = i; while (k <= j) { if (arr[k] % 2 == 1) { break; } k++; } // Check whether all elements of a subarray // are even if (k == j + 1) { val = true; } // When all elements of a subarray are even if (val == true) { ans = Math.Max(ans, length); } } } return ans; } // Driver Code static void Main(string[] args) { int[] arr = { 9, 8, 5, 4, 4, 4, 2, 4, 1 }; int N = arr.Length; Console.WriteLine(MaxEvenSubarray(arr, N)); }} |
Javascript
// Function to find the Length of the// largest Subarray with only even elementsfunction maxEvenSubarray(arr) { // To store the final answer let ans = 0; // Find all Subarrays for (let i = 0; i < arr.length; i++) { // To store the length of the subarray let length = 0; for (let j = i; j < arr.length; j++) { // Increment the length length++; // Boolean variable to tell whether subarray // contains all even elements let val = false; let k = i; while (k <= j) { if (arr[k] % 2 === 1) { break; } k++; } // Check whether all elements of a subarray // are even if (k === j + 1) { val = true; } // When all elements of a subarray are even if (val) { ans = Math.max(ans, length); } } } return ans;}// Driver Code// Input arrayconst arr = [9, 8, 5, 4, 4, 4, 2, 4, 1];console.log(maxEvenSubarray(arr)); |
5
Time Complexity: O(N3), because of two nested loops to find all subarrays and the third loop is to check whether a subarray contains all even elements
Auxiliary Space: O(1), because no extra space has been used
The idea is to observe that the largest subarray with only even elements is the maximum number of contiguous even elements in the array. Therefore, the task now reduces to find the maximum number of contiguous even elements in the array.
To do this, traverse the array using two variables, ans and current_count. The variable ans stores the final answer and current_count stores the length of subarray with only even numbers.
Now whenever an even element is found, keep incrementing the current_count and whenever an ODD element is found take the maximum of ans and current_count and reset current_count to zero.
At the end, ans will store the length of largest subarray with only even elements.
Below is the implementation of the above approach:
C++
// C++ Program to find the Length of the// largest Subarray with only even elements#include <cmath>#include <iostream>using namespace std;// Function to find the Length of the// largest Subarray with only even elementsint maxEvenSubarray(int array[], int N){ int ans = 0; int count = 0; // Iterate the loop for (int i = 0; i < N; i++) { // Check whether the element is // even in continuous fashion if (array[i] % 2 == 0) { count++; ans = max(ans, count); } else { // If element are not even in continuous // fashion, Reinitialize the count count = 0; } } // Check for the last element in the array ans = max(ans, count); return ans;}// Driver Codeint main(){ int arr[] = { 9, 8, 5, 4, 4, 4, 2, 4, 1 }; int N = sizeof(arr) / sizeof(arr[0]); cout << maxEvenSubarray(arr, N); return 0;} |
Java
// Java Program to find the Length of the longest// Subarray with only Even Elementspublic class GFG { // Function to find the Length of the longest // Subarray with only Even Elements static int maxEvenSubarray(int array[], int N) { int ans = 0; int count = 0; // Iterate the loop for (int i = 0; i < array.length; i++) { // Check whether the element is // even in continuous fashion if (array[i] % 2 == 0) { count++; ans = Math.max(ans, count); } else { // If element are not even in continuous // fashion. Reinitialize the count count = 0; } } // Check for the last element in the array ans = Math.max(ans, count); return ans; } // Driver Code public static void main(String args[]) { int arr[] = { 9, 8, 5, 4, 4, 4, 2, 4, 1 }; int N = arr.length; System.out.println(maxEvenSubarray(arr, N)); }} |
Python3
# Python3 Program to find the Length of the # largest Subarray with only even elements # Function to find the Length of the# largest Subarray with only even elementsdef maxEvenSubarray(array,N): ans = 0 count = 0 # Iterate the loop for i in range(0,N): # Check whether the element is # even in continuous fashion if array[i]%2==0: count +=1 ans = max(ans,count) else: # If element are not even in continuous # fashion, Reinitialize the count count = 0 # Check for the last element in the array ans = max(ans,count) return ans# Driver codeif __name__=='__main__': arr = [9, 8, 5, 4, 4, 4, 2, 4, 1] N = len(arr) print(maxEvenSubarray(arr,N))# This article is contributed by Shrikant13 |
C#
// C# Program to find the Length // of the largest Subarray with // only even elementsusing System;class GFG{// Function to find the Length // of the largest Subarray with// only even elementsstatic int maxEvenSubarray(int []array, int N){ int ans = 0; int count = 0; // Iterate the loop for (int i = 0; i < N; i++) { // Check whether the element is // even in continuous fashion if (array[i] % 2 == 0) { count++; ans = Math.Max(ans, count); } else { // If element are not even in // continuous fashion, // Reinitialize the count count = 0; } } // Check for the last // element in the array ans = Math.Max(ans, count); return ans;}// Driver Codepublic static void Main(){ int []arr = { 9, 8, 5, 4, 4, 4, 2, 4, 1 }; int N = arr.Length; Console.WriteLine(maxEvenSubarray(arr, N));}}// This code is contributed by ihritik |
Javascript
<script>// Javascript Program to find the Length// of the largest Subarray with// only even elements// Function to find the Length// of the largest Subarray with// only even elementsfunction maxEvenSubarray(array, N){ let ans = 0; let count = 0; // Iterate the loop for (let i = 0; i < N; i++) { // Check whether the element is // even in continuous fashion if (array[i] % 2 == 0) { count++; ans = Math.max(ans, count); } else { // If element are not even in // continuous fashion, // Reinitialize the count count = 0; } } // Check for the last // element in the array ans = Math.max(ans, count); return ans;}// Driver Codelet arr = new Array( 9, 8, 5, 4, 4, 4, 2, 4, 1 );let N = arr.length;document.write(maxEvenSubarray(arr, N));// This code is contributed by _saurabh_jaiswal.</script> |
PHP
<?php// PHP Program to find the Length // of the largest Subarray with // only even elements// Function to find the Length // of the largest Subarray with// only even elementsfunction maxEvenSubarray($array, $N){ $ans = 0; $count = 0; // Iterate the loop for ($i = 0; $i < $N; $i++) { // Check whether the element is // even in continuous fashion if ($array[$i] % 2 == 0) { $count++; $ans = max($ans, $count); } else { // If element are not even in // continuous fashion, // Reinitialize the count $count = 0; } } // Check for the last // element in the array $ans = max($ans, $count); return $ans;}// Driver Code$arr = array( 9, 8, 5, 4, 4, 4, 2, 4, 1 );$N = sizeof($arr);echo maxEvenSubarray($arr, $N);// This code is contributed by ihritik?> |
5
Time Complexity: O(N)
New Approach:- Here is another approach to solve this problem using dynamic programming.
Algorithm:-
1. Start by defining the function `maxEvenSubarray` that takes an integer array `arr` and its size `N` as input. This function returns an integer representing the length of the largest subarray with only even elements.
2. Initialize a variable `ans` to 0, which will store the length of the longest subarray.
3. Create a dynamic programming (DP) array `dp` of size `N` to store the lengths of subarrays with only even elements.
4. Initialize all elements of the `dp` array to 0 using a loop that iterates over the indices from 0 to `N-1`.
5. Iterate through the input array `arr` using a loop that goes from 0 to `N-1`. Let the current index be `i`.
6. Check if the element at index `i` in `arr` is even. If it is, perform the following steps:
a. If `i` is greater than 0, it means there is a previous element. In this case, update `dp[i]` to be equal to `dp[i-1] + 1`, indicating that the current element extends the length of the previous subarray with even elements.
b. If `i` is 0, it means the current element starts a new subarray with even elements. In this case, set `dp[i]` to 1.
7. After updating `dp[i]`, update the `ans` variable to be the maximum of `ans` and `dp[i]`. This keeps track of the maximum length found so far.
8. Repeat steps 5 to 7 for all elements in the input array.
9. After the loop completes, the `ans` variable will hold the length of the largest subarray with only even elements.
10. Return `ans` as the result of the function.
11. In the `main` function, create an input array `arr` with some values and calculate its size `N`.
12. Call the `maxEvenSubarray` function with `arr` and `N` as arguments, and store the returned result in a variable.
13. Print the result using `cout`.
14. End the program by returning 0.
Below is the implementation of the above approach:
C++
#include <iostream>using namespace std;// Function to find the Length of the// largest Subarray with only even elementsint maxEvenSubarray(int arr[], int N){ int ans = 0; // Create a dp array to store the lengths // of subarrays with only even elements int dp[N]; // Initialize dp array with 0 for (int i = 0; i < N; i++) dp[i] = 0; // Update dp array for (int i = 0; i < N; i++) { if (arr[i] % 2 == 0) { if (i > 0) dp[i] = dp[i - 1] + 1; else dp[i] = 1; } // Update the answer ans = max(ans, dp[i]); } return ans;}// Driver Codeint main(){ int arr[] = { 9, 8, 5, 4, 4, 4, 2, 4, 1 }; int N = sizeof(arr) / sizeof(arr[0]); cout << maxEvenSubarray(arr, N); return 0;} |
Java
public class Main { // Function to find the Length of the // largest Subarray with only even elements static int maxEvenSubarray(int[] arr, int N) { int ans = 0; // Create a dp array to store the lengths // of subarrays with only even elements int[] dp = new int[N]; // Initialize dp array with 0 for (int i = 0; i < N; i++) { dp[i] = 0; } // Update dp array for (int i = 0; i < N; i++) { if (arr[i] % 2 == 0) { if (i > 0) dp[i] = dp[i - 1] + 1; else dp[i] = 1; } // Update the answer ans = Math.max(ans, dp[i]); } return ans; } // Driver Code public static void main(String[] args) { int[] arr = { 9, 8, 5, 4, 4, 4, 2, 4, 1 }; int N = arr.length; System.out.println(maxEvenSubarray(arr, N)); }}// This code is contributed by shivamgupta0987654321 |
5
The time complexity:- of the provided code is O(N), where N is the size of the input array `arr`. This is because the code iterates through the array only once in a single loop.
The auxiliary space:- of the code is O(N) as well. This is due to the creation of the `dp` array, which has the same size as the input array `arr`. The additional space used by the code is proportional to the input size.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
