Given an array A[ ] of N non-negative integers, the task is to find the length of the longest sub-array such that all the elements in that sub-array are odd or even.
Examples:
Input: A[] = {2, 5, 7, 2, 4, 6, 8, 3}
Output: 4
Explanation: Sub-array {2, 4, 6, 8} of length 4 has all even elementsInput: A[] = {2, 3, 2, 5, 7, 3}
Output: 3
Explanation: Sub-array {5, 7, 3} of length 3 has all odd elements
Naive Approach: A naive approach to solve this problem is to consider all the contiguous sub-arrays and for each sub-array, check if all the elements are even or odd. The longest of them will be the answer.
Steps to implement:
- Declare a variable “ans” with value 0 because if no such subarray exists then 0 will be the answer
- Run two nested loops to find all subarrays
- Find the length of each subarray
- Make a boolean variable for each subarray that will initially contain false and when that subarray has all elements even or all elements odd then make that boolean variable true.
- If the boolean variable is true for any subarray, it is the required subarray. So update ans as the maximum of ans and the length of that subarray.
Code-
C++
// C++ implementation for the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate longest substring // with odd or even elements int LongestOddEvenSubarray( int arr[], int N) { //Value to store final answer int ans=0; 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++; //This will tell that subarray contains all //odd or all even bool val= false ; //Check for all elements are even int k=i; while (k<=j){ if (arr[k]%2!=0){ break ;} k++; } //when all elements are even if (k==j+1){val= true ;} //Check for all elements are odd k=i; while (k<=j){ if (arr[k]%2!=1){ break ;} k++; } //when all elements are odd if (k==j+1){val= true ;} //Update answer when all elements are even or odd if (val== true ){ ans=max(ans,length); } } } return ans; } // Driver Code int main() { // Input int arr[] = { 2, 5, 7, 2, 4, 6, 8, 3 }; int N = sizeof (arr) / sizeof (arr[0]); // Function call cout << LongestOddEvenSubarray(arr, N); return 0; } |
Python3
# Function to calculate the longest substring # with either all odd or all even elements def longest_odd_even_subarray(arr, N): # Variable to store the final answer ans = 0 for i in range (N): # To store the length of the subarray length = 0 for j in range (i, N): # Increment the length length + = 1 # This will tell us if the subarray contains all # odd or all even elements val = False # Check if all elements are even k = i while k < = j: if arr[k] % 2 ! = 0 : break k + = 1 # When all elements are even if k = = j + 1 : val = True # Check if all elements are odd k = i while k < = j: if arr[k] % 2 ! = 1 : break k + = 1 # When all elements are odd if k = = j + 1 : val = True # Update the answer when all elements are even or odd if val: ans = max (ans, length) return ans # Driver Code if __name__ = = "__main__" : # Input arr = [ 2 , 5 , 7 , 2 , 4 , 6 , 8 , 3 ] N = len (arr) # Function call print (longest_odd_even_subarray(arr, N)) |
4
Time Complexity: O(N3), because of two nested loops to find all subarray and the third loop is for finding that subarray contains all elements odd or all elements even
Auxiliary Space: O(1), because no extra space has been used
Efficient Approach: The main idea to solve this problem is to use Dynamic Programming(it has both the properties – Optimal Substructure and Overlapping Subproblems) such that if there are some contiguous odd elements, then the very next odd element will increase the length of that contiguous array by one. And this is also true for even elements. Follow the steps below to solve the problem:
- Initialize an array dp[ ] where dp[i] stores the length of sub-array that ends at A[i].
- Initialize dp[0] with 1.
- Initialize the variable ans as 1 to store the answer.
- Iterate over the range [1, N] using the variable i and perform the following steps:
- If A[i]%2 is equal to A[i-1]%2, then set the value of dp[i] as dp[i-1]+1.
- Else, set the value of dp[i] as 1.
- Iterate over the range [0, N] using the variable i and perform the following steps:
- Set the value of ans as the maximum of ans or dp[i].
- After performing the above steps, print the value of ans as the answer.
Below is the implementation of the above approach:
C++
// C++ implementation for the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate longest substring // with odd or even elements int LongestOddEvenSubarray( int A[], int N) { // Initializing dp[] int dp[N]; // Initializing dp[0] with 1 dp[0] = 1; // ans will store the final answer int ans = 1; // Traversing the array from index 1 to N - 1 for ( int i = 1; i < N; i++) { // Checking both current and previous element // is even or odd if ((A[i] % 2 == 0 && A[i - 1] % 2 == 0) || (A[i] % 2 != 0 && A[i - 1] % 2 != 0)) { // Updating dp[i] with dp[i-1] + 1 dp[i] = dp[i - 1] + 1; } else dp[i] = 1; } for ( int i = 0; i < N; i++) // Storing max element to ans ans = max(ans, dp[i]); // Returning the final answer return ans; } // Driver Code int main() { // Input int A[] = { 2, 5, 7, 2, 4, 6, 8, 3 }; int N = sizeof (A) / sizeof (A[0]); // Function call cout << LongestOddEvenSubarray(A, N); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG { // Function to calculate longest substring // with odd or even elements static int LongestOddEvenSubarray( int A[], int N) { // Initializing dp[] int dp[] = new int [N]; // Initializing dp[0] with 1 dp[ 0 ] = 1 ; // ans will store the final answer int ans = 1 ; // Traversing the array from index 1 to N - 1 for ( int i = 1 ; i < N; i++) { // Checking both current and previous element // is even or odd if ((A[i] % 2 == 0 && A[i - 1 ] % 2 == 0 ) || (A[i] % 2 != 0 && A[i - 1 ] % 2 != 0 )) { // Updating dp[i] with dp[i-1] + 1 dp[i] = dp[i - 1 ] + 1 ; } else dp[i] = 1 ; } for ( int i = 0 ; i < N; i++) // Storing max element to ans ans = Math.max(ans, dp[i]); // Returning the final answer return ans; } // Driver Code public static void main(String[] args) { // Input int A[] = { 2 , 5 , 7 , 2 , 4 , 6 , 8 , 3 }; int N = A.length; // Function call System.out.println(LongestOddEvenSubarray(A, N)); } } // This code is contributed by Potta Lokesh |
Python3
# Python 3 implementation for the above approach # Function to calculate longest substring # with odd or even elements def LongestOddEvenSubarray(A, N): # Initializing dp[] dp = [ 0 for i in range (N)] # Initializing dp[0] with 1 dp[ 0 ] = 1 # ans will store the final answer ans = 1 # Traversing the array from index 1 to N - 1 for i in range ( 1 , N, 1 ): # Checking both current and previous element # is even or odd if ((A[i] % 2 = = 0 and A[i - 1 ] % 2 = = 0 ) or (A[i] % 2 ! = 0 and A[i - 1 ] % 2 ! = 0 )): # Updating dp[i] with dp[i-1] + 1 dp[i] = dp[i - 1 ] + 1 else : dp[i] = 1 for i in range (N): # Storing max element to ans ans = max (ans, dp[i]) # Returning the final answer return ans # Driver Code if __name__ = = '__main__' : # Input A = [ 2 , 5 , 7 , 2 , 4 , 6 , 8 , 3 ] N = len (A) # Function call print (LongestOddEvenSubarray(A, N)) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approach using System; class GFG{ // Function to calculate longest substring // with odd or even elements static int LongestOddEvenSubarray( int [] A, int N) { // Initializing dp[] int [] dp = new int [N]; // Initializing dp[0] with 1 dp[0] = 1; // ans will store the final answer int ans = 1; // Traversing the array from index 1 to N - 1 for ( int i = 1; i < N; i++) { // Checking both current and previous element // is even or odd if ((A[i] % 2 == 0 && A[i - 1] % 2 == 0) || (A[i] % 2 != 0 && A[i - 1] % 2 != 0)) { // Updating dp[i] with dp[i-1] + 1 dp[i] = dp[i - 1] + 1; } else dp[i] = 1; } for ( int i = 0; i < N; i++) // Storing max element to ans ans = Math.Max(ans, dp[i]); // Returning the final answer return ans; } // Driver Code public static void Main() { // Input int [] A = { 2, 5, 7, 2, 4, 6, 8, 3 }; int N = A.Length; // Function call Console.Write(LongestOddEvenSubarray(A, N)); } } // This code is contributed by target_2. |
Javascript
<script> // JavaScript implementation for the above approach // Function to calculate longest substring // with odd or even elements function LongestOddEvenSubarray(A, N) { // Initializing dp[] let dp = new Array(N); // Initializing dp[0] with 1 dp[0] = 1; // ans will store the final answer let ans = 1; // Traversing the array from index 1 to N - 1 for (let i = 1; i < N; i++) { // Checking both current and previous element // is even or odd if ( (A[i] % 2 == 0 && A[i - 1] % 2 == 0) || (A[i] % 2 != 0 && A[i - 1] % 2 != 0) ) { // Updating dp[i] with dp[i-1] + 1 dp[i] = dp[i - 1] + 1; } else dp[i] = 1; } for (let i = 0; i < N; i++) // Storing max element to ans ans = Math.max(ans, dp[i]); // Returning the final answer return ans; } // Driver Code // Input let A = [2, 5, 7, 2, 4, 6, 8, 3]; let N = A.length; // Function call document.write(LongestOddEvenSubarray(A, N)); // This code is contributed by _saurabh_jaiswal. </script> |
4
Time Complexity: O(N)
Auxiliary Space: O(N)
Space Optimization: It is possible to further optimize the space complexity of the above approach by observing that, for calculating dp[i], only the value of dp[i-1] is relevant. So, store dp[i-1] in a variable and update the variable in each iteration. Also, update the answer in each iteration. Follow the steps below to solve the problem:
- Initialize the variables dp as 1 to store the length of the sub-array till i-1 and ans as 1 to store the answer.
- Iterate over the range [1, N] using the variable i and perform the following steps:
- If A[i]%2 is equal to A[i-1]%2, then set the value of dp as dp+1 and set the value of ans as the maximum of ans or dp.
- Else, set the value of dp as 1.
- After performing the above steps, print the value of ans as the answer.
Below is the implementation of the above approach:
C++
// C++ implementation for the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate longest substring // with odd or even elements int LongestOddEvenSubarray( int A[], int N) { // Initializing dp int dp; // Initializing dp with 1 dp = 1; // ans will store the final answer int ans = 1; // Traversing the array from index 1 to N - 1 for ( int i = 1; i < N; i++) { // Checking both current and previous element // is even or odd if ((A[i] % 2 == 0 && A[i - 1] % 2 == 0) || (A[i] % 2 != 0 && A[i - 1] % 2 != 0)) { // Updating dp with (previous dp value) + 1 dp = dp + 1; // Storing max element so far to ans ans = max(ans, dp); } else dp = 1; } // Returning the final answer return ans; } // Driver code int main() { // Input int A[] = { 2, 5, 7, 2, 4, 6, 8, 3 }; int N = sizeof (A) / sizeof (A[0]); // Function call cout << LongestOddEvenSubarray(A, N); return 0; } |
Java
// Java implementation for the above approach import java.util.*; class GFG { // Function to calculate longest subString // with odd or even elements static int LongestOddEvenSubarray( int A[], int N) { // Initializing dp int dp; // Initializing dp with 1 dp = 1 ; // ans will store the final answer int ans = 1 ; // Traversing the array from index 1 to N - 1 for ( int i = 1 ; i < N; i++) { // Checking both current and previous element // is even or odd if ((A[i] % 2 == 0 && A[i - 1 ] % 2 == 0 ) || (A[i] % 2 != 0 && A[i - 1 ] % 2 != 0 )) { // Updating dp with (previous dp value) + 1 dp = dp + 1 ; // Storing max element so far to ans ans = Math.max(ans, dp); } else dp = 1 ; } // Returning the final answer return ans; } // Driver code public static void main(String[] args) { // Input int A[] = { 2 , 5 , 7 , 2 , 4 , 6 , 8 , 3 }; int N = A.length; // Function call System.out.print(LongestOddEvenSubarray(A, N)); } } // This code is contributed by Amit Katiyar |
Python3
# Python implementation for the above approach # Function to calculate longest substring # with odd or even elements def LongestOddEvenSubarray(A, N): # Initializing dp # Initializing dp with 1 dp = 1 # ans will store the final answer ans = 1 # Traversing the array from index 1 to N - 1 for i in range ( 1 , N): # Checking both current and previous element # is even or odd if ((A[i] % 2 = = 0 and A[i - 1 ] % 2 = = 0 ) or (A[i] % 2 ! = 0 and A[i - 1 ] % 2 ! = 0 )): # Updating dp with (previous dp value) + 1 dp = dp + 1 # Storing max element so far to ans ans = max (ans, dp) else : dp = 1 # Returning the final answer return ans # Driver code # Input A = [ 2 , 5 , 7 , 2 , 4 , 6 , 8 , 3 ] N = len (A) # Function call print (LongestOddEvenSubarray(A, N)) # This code is contributed by shivani |
C#
// C# implementation for the above approach using System; public class GFG { // Function to calculate longest subString // with odd or even elements static int longestOddEvenSubarray( int []A, int N) { // Initializing dp int dp; // Initializing dp with 1 dp = 1; // ans will store the readonly answer int ans = 1; // Traversing the array from index 1 to N - 1 for ( int i = 1; i < N; i++) { // Checking both current and previous element // is even or odd if ((A[i] % 2 == 0 && A[i - 1] % 2 == 0) || (A[i] % 2 != 0 && A[i - 1] % 2 != 0)) { // Updating dp with (previous dp value) + 1 dp = dp + 1; // Storing max element so far to ans ans = Math.Max(ans, dp); } else dp = 1; } // Returning the readonly answer return ans; } // Driver code public static void Main(String[] args) { // Input int []A = { 2, 5, 7, 2, 4, 6, 8, 3 }; int N = A.Length; // Function call Console.Write(longestOddEvenSubarray(A, N)); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript implementation for the above approach // Function to calculate longest substring // with odd or even elements function LongestOddEvenSubarray(A, N) { // Initializing dp let dp; // Initializing dp with 1 dp = 1; // ans will store the final answer let ans = 1; // Traversing the array from index 1 to N - 1 for (let i = 1; i < N; i++) { // Checking both current and previous element // is even or odd if ( (A[i] % 2 == 0 && A[i - 1] % 2 == 0) || (A[i] % 2 != 0 && A[i - 1] % 2 != 0) ) { // Updating dp with (previous dp value) + 1 dp = dp + 1; // Storing max element so far to ans ans = Math.max(ans, dp); } else dp = 1; } // Returning the final answer return ans; } // Driver code // Input let A = [2, 5, 7, 2, 4, 6, 8, 3]; let N = A.length; // Function call document.write(LongestOddEvenSubarray(A, N)); </script> |
4
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!