Given an array of N elements. The task is to find the length of the longest subarray such that sum of the subarray is even.
Examples:
Input : N = 6, arr[] = {1, 2, 3, 2, 1, 4}
Output : 5
Explanation: In the example the subarray
in range [2, 6] has sum 12 which is even,
so the length is 5.
Input : N = 4, arr[] = {1, 2, 3, 2}
Output : 4
Naive Approach
The idea is to find all subarrays and then find those subarrays whose sum of elements are even. After that choose the longest length of those subarrays.
Steps to implement-
- Declare a variable ans with value 0 to store the final answer
- Run two loops to find all subarrays
- Find the sum of all elements of the subarray
- When the sum of all elements of the subarray is even
- Then update ans as the maximum of ans and the length of that subarray
Code-
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to find length of the longest// subarray such that sum of the// subarray is evenint maxLength(int arr[], int N){ //To store 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 variable to tell whether sum //of all elements are even or not bool val=false; //To store sum of all elements of subarray int sum=0; for(int k=i;k<=j;k++){ sum+=arr[k]; } //When sum of all elements are even if(sum%2==0){ ans=max(ans,length); } } } return ans;}// Driver Codeint main(){ int arr[] = { 1, 2, 3, 2 }; int N = sizeof(arr) / sizeof(arr[0]); cout << maxLength(arr, N) << "\n"; return 0;} |
Java
// Java implementation of the above approachimport java.util.*;public class Main { // Function to find length of the longest // subarray such that sum of the // subarray is even static int maxLength(int[] arr, int N) { // To store 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 variable to tell whether sum // of all elements are even or not boolean val = false; // To store sum of all elements of subarray int sum = 0; for (int k = i; k <= j; k++) { sum += arr[k]; } // When sum of all elements is even if (sum % 2 == 0) { ans = Math.max(ans, length); } } } return ans; } // Driver Code public static void main(String[] args) { int[] arr = {1, 2, 3, 2}; int N = arr.length; System.out.println(maxLength(arr, N)); }}// This code is contributed by Pushpesh Raj |
Python3
# Python3 implementation of the above approach# Function to find length of the longest subarray such # that sum of the subarray is evendef maxLength(arr): # To store the answer ans = 0 # Find all subarrays for i in range(len(arr)): # To store the length of subarray length = 0 for j in range(i, len(arr)): # Increment the length length += 1 # Boolean variable to tell whether the sum # of all elements is even or not val = False # To store the sum of all elements of subarray subarray_sum = 0 for k in range(i, j + 1): subarray_sum += arr[k] # When the sum of all elements is even if subarray_sum % 2 == 0: ans = max(ans, length) return ans# Driver Codearr = [1, 2, 3, 2]print(maxLength(arr)) |
C#
using System;public class GFG{ // Function to find length of the longest // subarray such that sum of the // subarray is even public static int MaxLength(int[] arr, int N) { // To store the 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++; // To store the sum of all elements of subarray int sum = 0; for (int k = i; k <= j; k++) { sum += arr[k]; } // When the sum of all elements is even if (sum % 2 == 0) { ans = Math.Max(ans, length); } } } return ans; } // Driver code public static void Main(string[] args) { int[] arr = { 1, 2, 3, 2 }; int N = arr.Length; Console.WriteLine(MaxLength(arr, N)); }} |
Javascript
function MaxLength(arr, N) { // To store the answer let ans = 0; // Find all subarrays for (let i = 0; i < N; i++) { // To store the length of subarray let length = 0; for (let j = i; j < N; j++) { // Increment the length length++; // To store the sum of all elements of subarray let sum = 0; for (let k = i; k <= j; k++) { sum += arr[k]; } // When the sum of all elements is even if (sum % 2 === 0) { ans = Math.max(ans, length); } } } return ans;}// Driver codeconst arr = [1, 2, 3, 2];const N = arr.length;console.log(MaxLength(arr, N)); |
Output
4
Time Complexity: O(N3), because of two nested loops to find all subarray and third loop is to find the sum of all elements of subarray
Auxiliary Space: O(1), because no extra space has been used
Approach: First check if the total sum of the array is even. If the total sum of the array is even then the answer will be N.
If the total sum of the array is not even, means it is ODD. So, the idea is to find an odd element from the array such that excluding that element and comparing the length of both parts of the array we can obtain the max length of the subarray with even sum.
It is obvious that the subarray with even sum will exist in range [1, x) or (x, N],
where 1 <= x <= N, and arr[x] is ODD.
Below is the implementation of above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to find length of the longest// subarray such that sum of the// subarray is evenint maxLength(int a[], int n){ int sum = 0, len = 0; // Check if sum of complete array is even for (int i = 0; i < n; i++) sum += a[i]; if (sum % 2 == 0) // total sum is already even return n; // Find an index i such the a[i] is odd // and compare length of both halves excluding // a[i] to find max length subarray for (int i = 0; i < n; i++) { if (a[i] % 2 == 1) len = max(len, max(n - i - 1, i)); } return len;}// Driver Codeint main(){ int a[] = { 1, 2, 3, 2 }; int n = sizeof(a) / sizeof(a[0]); cout << maxLength(a, n) << "\n"; return 0;} |
Java
// Java implementation of the approachclass GFG { // Function to find length of the longest // subarray such that sum of the // subarray is even static int maxLength(int a[], int n) { int sum = 0, len = 0; // Check if sum of complete array is even for (int i = 0; i < n; i++) { sum += a[i]; } if (sum % 2 == 0) // total sum is already even { return n; } // Find an index i such the a[i] is odd // and compare length of both halfs excluding // a[i] to find max length subarray for (int i = 0; i < n; i++) { if (a[i] % 2 == 1) { len = Math.max(len, Math.max(n - i - 1, i)); } } return len; } // Driver Code public static void main(String[] args) { int a[] = {1, 2, 3, 2}; int n = a.length; System.out.println(maxLength(a, n)); }}// This code has been contributed by 29AjayKumar |
Python
# Python3 implementation of the above approach# Function to find Length of the longest# subarray such that Sum of the# subarray is evendef maxLength(a, n): Sum = 0 Len = 0 # Check if Sum of complete array is even for i in range(n): Sum += a[i] if (Sum % 2 == 0): # total Sum is already even return n # Find an index i such the a[i] is odd # and compare Length of both halfs excluding # a[i] to find max Length subarray for i in range(n): if (a[i] % 2 == 1): Len = max(Len, max(n - i - 1, i)) return Len# Driver Codea= [1, 2, 3, 2]n = len(a)print(maxLength(a, n))# This code is contributed by mohit kumar |
C#
// C# implementation of the approachusing System;class GFG{ // Function to find length of the longest // subarray such that sum of the // subarray is even static int maxLength(int []a, int n) { int sum = 0, len = 0; // Check if sum of complete array is even for (int i = 0; i < n; i++) { sum += a[i]; } if (sum % 2 == 0) // total sum is already even { return n; } // Find an index i such the a[i] is odd // and compare length of both halfs excluding // a[i] to find max length subarray for (int i = 0; i < n; i++) { if (a[i] % 2 == 1) { len = Math.Max(len, Math.Max(n - i - 1, i)); } } return len; } // Driver Code static public void Main () { int []a = {1, 2, 3, 2}; int n = a.Length; Console.WriteLine(maxLength(a, n)); }}// This code has been contributed by ajit. |
Javascript
<script>// Javascript implementation of the above approach // Function to find length of the longest // subarray such that sum of the // subarray is even function maxLength(a, n) { let sum = 0, len = 0; // Check if sum of complete array is even for (let i = 0; i < n; i++) sum += a[i]; if (sum % 2 == 0) // total sum is already even return n; // Find an index i such the a[i] is odd // and compare length of both halfs excluding // a[i] to find max length subarray for (let i = 0; i < n; i++) { if (a[i] % 2 == 1) len = Math.max(len, Math.max(n - i - 1, i)); } return len; } // Driver Code let a = [ 1, 2, 3, 2 ]; let n = a.length; document.write(maxLength(a, n) + "<br>"); // This code is contributed by Mayank Tyagi</script> |
PHP
<?php//PHP implementation of the above approach// Function to find length of the longest// subarray such that sum of the// subarray is evenfunction maxLength($a, $n){ $sum = 0; $len = 0; // Check if sum of complete array is even for ($i = 0; $i < $n; $i++) $sum += $a[$i]; if ($sum % 2 == 0) // total sum is already even return $n; // Find an index i such the a[i] is odd // and compare length of both halfs excluding // a[i] to find max length subarray for ($i = 0; $i < $n; $i++) { if ($a[$i] % 2 == 1) $len = max($len, $max($n - $i - 1, $i)); } return $len;}// Driver Code$a = array (1, 2, 3, 2 );$n = count($a);echo maxLength($a, $n) , "\n";// This code is contributed by akt_mit.?> |
Output
4
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!
