Given an array arr[] of size N, the task is to find the largest element in the longest subarray consisting only of even numbers or odd numbers.
Examples:
Input: arr[] = { 2, 4, 6, 9, 10, 11 }
Output: 6
Explanation:
The longest subarray consisting of only even or odd numbers is { arr[0], arr[1], arr[2] }.
Since the largest element of the subarray is arr[2], the required output is 6.Input: arr[] = { 3, 5, 7, 4, 9, 11, 13 }
Output: 13
Explanation:
The longest subarray consisting of only even or odd numbers are { {3, 5, 7 }, { 9, 11, 13 } }.
The largest elements in the subarrays are 7 and 13 respectively. 13 being the largest, is the required output.
Naive Approach
The idea is to find all subarrays and in that find those subarrays whose all elements are even or all elements are odd. Then in those subarrays find the longest subarray and then the largest element of that longest subarray.
Steps to implement-
- Declare a variable temp to store the length of the required longest subarray
- Declare a variable ans to store the largest element of the required longest subarray
- Run two for loops to find all subarrays and simultaneously find the length of the subarray and the largest element present in that subarray
- Pick that sub-array which contain all even elements or odd elements
- Then if that subarray has the longest length till now from all other subarrays which contain all even elements or all odd elements
- Then update ans with the maximum of ans and the largest element present in that subarray
Code-
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the largest element// of the longest subarray consisting// only of odd or even elements onlyint maxelementLongestSub(int arr[], int N){ //To store longest subarray whose all elements are even //or all elements are odd int temp=0; //To store final answer int ans=INT_MIN; for(int i=0;i<N;i++){ //To store length of subarray int length=0; //To store largest element of that subarray int largest=INT_MIN; for(int j=i;j<N;j++){ //Increment the length length++; //Find largest element largest=max(largest,arr[j]); //This will tell that subarray contains all //odd or all even bool val=false; //Check 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 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 and satisfy input condition if(val==true){ if(length>=temp){ temp=length; ans=max(ans,largest); } } } } return ans; }// Driver Codeint main(){ int arr[] = { 1, 3, 5, 7, 8, 12, 10 }; int N = sizeof(arr) / sizeof(arr[0]); cout << maxelementLongestSub(arr, N); return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;public class GFG { // Function to find the largest element // of the longest subarray consisting // only of odd or even elements only static int maxelementLongestSub(int[] arr, int N) { // To store the longest subarray whose all elements // are even or all elements are odd int temp = 0; // To store the final answer int ans = Integer.MIN_VALUE; for (int i = 0; i < N; i++) { // To store the length of the subarray int length = 0; // To store the largest element of that subarray int largest = Integer.MIN_VALUE; for (int j = i; j < N; j++) { // Increment the length length++; // Find the largest element largest = Math.max(largest, arr[j]); // This will tell if the subarray contains // all odd or all even elements boolean val = false; // Check if 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 if 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 and satisfy input condition if (val == true) { if (length >= temp) { temp = length; ans = Math.max(ans, largest); } } } } return ans; } // Driver Code public static void main(String[] args) { int[] arr = { 1, 3, 5, 7, 8, 12, 10 }; int N = arr.length; System.out.println(maxelementLongestSub(arr, N)); }} |
Python3
# Function to find the largest element# of the longest subarray consisting# only of odd or even elements onlydef maxelementLongestSub(arr, N): # To store longest subarray whose all elements are even # or all elements are odd temp = 0 # To store final answer ans = float("-inf") for i in range(N): # To store length of subarray length = 0 # To store largest element of that subarray largest = float("-inf") for j in range(i, N): # Increment the length length += 1 # Find the largest element largest = max(largest, arr[j]) # This will tell that subarray contains all # odd or all even val = False # Check 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 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 answer when all elements are even or odd and satisfy input condition if val: if length >= temp: temp = length ans = max(ans, largest) return ans# Driver Codeif __name__ == "__main__": arr = [1, 3, 5, 7, 8, 12, 10] N = len(arr) print(maxelementLongestSub(arr, N)) |
C#
using System;public class GFG{ // Function to find the largest element // of the longest subarray consisting // only of odd or even elements only static int MaxElementLongestSub(int[] arr, int N) { // To store the longest subarray whose all elements // are even or all elements are odd int temp = 0; // To store the final answer int ans = int.MinValue; for (int i = 0; i < N; i++) { // To store the length of the subarray int length = 0; // To store the largest element of that subarray int largest = int.MinValue; for (int j = i; j < N; j++) { // Increment the length length++; // Find the largest element largest = Math.Max(largest, arr[j]); // This will tell if the subarray contains // all odd or all even elements bool val = false; // Check if 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 if 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 the answer when all elements are even // or odd and satisfy the input condition if (val == true) { if (length >= temp) { temp = length; ans = Math.Max(ans, largest); } } } } return ans; } // Driver Code public static void Main(string[] args) { int[] arr = { 1, 3, 5, 7, 8, 12, 10 }; int N = arr.Length; Console.WriteLine(MaxElementLongestSub(arr, N)); }} |
Javascript
// JavaScript program to implement// the above approach// Function to find the largest element// of the longest subarray consisting// only of odd or even elements onlyfunction maxelementLongestSub(arr, N){//To store longest subarray whose all elements are even//or all elements are oddlet temp=0; //To store final answerlet ans=Number. MIN_VALUE; for(let i=0;i<N;i++){ //To store length of subarray let length=0; //To store largest element of that subarray let largest=Number. MIN_VALUE; for(let j=i;j<N;j++){ //Increment the length length++; //Find largest element largest=Math.max(largest,arr[j]); //This will tell that subarray contains all //odd or all even let val=false; //Check all elements are even let k=i; while(k<=j){ if(arr[k]%2!=0){break;} k++; } //when all elements are even if(k==j+1){val=true;} //Check 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 and satisfy input condition if(val==true){ if(length>=temp){ temp=length; ans=Math.max(ans,largest); } } }}return ans;}// Driver Code let arr = [ 1, 3, 5, 7, 8, 12, 10 ]; let N = arr.length; console.log(maxelementLongestSub(arr, N)); |
Output-
7
Time Complexity: O(N3), because of two nested loops to find all subarray and a third loop to find that subarray contains all even elements or odd elements
Auxiliary Space: O(1), because no extra space has been used
Approach: Follow the steps below to solve the problem:
- Initialize a variable, say maxLen, to store the length of the longest subarray obtained till ith index, which contains either even numbers or odd numbers only.
- Initialize a variable, say Len, to store the length of the current subarray upto the ith array element, consisting only of even or odd numbers.
- Initialize a variable, say MaxElem, to store the largest element of the longest subarray obtained till ith index which consists only of even or odd elements.
- Traverse the array using variable i. For every ith array element, check if arr[i] % 2 is equal to arr[i – 1] % 2 or not. If found to be true, then increment the value of Len.
- Otherwise, update the value of Len = 1.
- If Len >= maxLen, then update MaxElem = max(MaxElem, arr[i]).
- Finally, print the value of MaxElem.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <iostream>using namespace std;// Function to find the largest element// of the longest subarray consisting// only of odd or even elements onlyint maxelementLongestSub(int arr[], int n){ // Stores largest element of the // longest subarray till i-th index int MaxElem = arr[0]; // Stores maximum length of the // longest subarray till i-th index int maxLen = 1; // Stores length of the current // subarray including the i-th element int Len = 1; // Stores largest element in // current subarray int Max = arr[0]; // Traverse the array for (int i = 1; i < n; i++) { // If arr[i] and arr[i - 1] // are either even numbers // or odd numbers if (arr[i] % 2 == arr[i - 1] % 2) { // Update Len Len++; // Update Max if (arr[i] > Max) Max = arr[i]; // If Len greater than // maxLen if (Len >= maxLen) { maxLen = Len; // Update MaxElem if (Max >= MaxElem) MaxElem = Max; } } else { // Update Len Len = 1; // Update Max Max = arr[i]; // If Len greater // than maxLen if (Len >= maxLen) { // Update maxLen maxLen = Len; // If Max greater // than MaxElem if (Max >= MaxElem) { // Update MaxElem MaxElem = Max; } } } } return MaxElem;}// Driver Codeint main(){ int arr[] = { 1, 3, 5, 7, 8, 12, 10 }; int n = sizeof(arr) / sizeof(arr[0]); cout << maxelementLongestSub(arr, n); return 0;} |
C
// C program to implement// the above approach#include <stdio.h>// Function to find the largest element// of the longest subarray consisting// only of odd or even elements onlyint maxelementLongestSub(int arr[], int n){ // Stores largest element of the // longest subarray till i-th index int MaxElem = arr[0]; // Stores maximum length of the // longest subarray till i-th index int maxLen = 1; // Stores length of the current // subarray including the i-th element int Len = 1; // Stores largest element in // current subarray int Max = arr[0]; // Traverse the array for(int i = 1; i < n; i++) { // If arr[i] and arr[i - 1] // are either even numbers // or odd numbers if (arr[i] % 2 == arr[i - 1] % 2) { // Update Len Len++; // Update Max if (arr[i] > Max) Max = arr[i]; // If Len greater than // maxLen if (Len >= maxLen) { maxLen = Len; // Update MaxElem if (Max >= MaxElem) MaxElem = Max; } } else { // Update Len Len = 1; // Update Max Max = arr[i]; // If Len greater // than maxLen if (Len >= maxLen) { // Update maxLen maxLen = Len; // If Max greater // than MaxElem if (Max >= MaxElem) { // Update MaxElem MaxElem = Max; } } } } return MaxElem;}// Driver Codeint main(){ int arr[] = { 1, 3, 5, 7, 8, 12, 10 }; int n = sizeof(arr) / sizeof(arr[0]); printf("%d", maxelementLongestSub(arr, n)); return 0;}// This code is contributed by sourav singh |
Java
// Java program to implement // the above approach import java.io.*;class GFG{// Function to find the largest element // of the longest subarray consisting // only of odd or even elements only static int maxelementLongestSub(int arr[], int n){ // Stores largest element of the // longest subarray till i-th index int MaxElem = arr[0]; // Stores maximum length of the // longest subarray till i-th index int maxLen = 1; // Stores length of the current // subarray including the i-th element int Len = 1; // Stores largest element in // current subarray int Max = arr[0]; // Traverse the array for(int i = 1; i < n; i++) { // If arr[i] and arr[i - 1] // are either even numbers // or odd numbers if (arr[i] % 2 == arr[i - 1] % 2) { // Update Len Len++; // Update Max if (arr[i] > Max) Max = arr[i]; // If Len greater than // maxLen if (Len >= maxLen) { maxLen = Len; // Update MaxElem if (Max >= MaxElem) MaxElem = Max; } } else { // Update Len Len = 1; // Update Max Max = arr[i]; // If Len greater // than maxLen if (Len >= maxLen) { // Update maxLen maxLen = Len; // If Max greater // than MaxElem if (Max >= MaxElem) { // Update MaxElem MaxElem = Max; } } } } return MaxElem;}// Driver Codepublic static void main(String[] args){ int arr[] = { 1, 3, 5, 7, 8, 12, 10 }; int n = arr.length; System.out.print(maxelementLongestSub(arr, n));}}// This code is contributed by sourav singh |
Python3
# Python3 program to implement# the above approach# Function to find the largest element # of the longest subarray consisting # only of odd or even elements only def maxelementLongestSub(arr, n): # Stores largest element of the # longest sub-array till i-th index MaxElem = arr[0] # Stores maximum length of the # longest sub-array till i-th index maxLen = 1 # Stores length of the current # sub-array including the i-th element Len = 1 # Stores largest element in # current sub-array Max = arr[0] for i in range(1, n): # If arr[i] and arr[i - 1] # are either even numbers # or odd numbers if arr[i] % 2 == arr[i - 1] % 2: # Update Len Len += 1 # Update Max if arr[i] > Max: Max = arr[i] # If Len greater than # maxLen if Len >= maxLen: maxLen = Len # Update MaxElem if Max >= MaxElem: MaxElem = Max else: # Update Len Len = 1 # Update Max Max = arr[i] # If Len greater # than maxLen if Len >= maxLen: maxLen = Len # If Max greater # than MaxElem if Max >= MaxElem: MaxElem = Max return MaxElem# Driver Codearr = [ 1, 3, 5, 7, 8, 12, 10 ]n = len(arr)print(maxelementLongestSub(arr, n))# This code is contributed by sourav singh |
C#
// C# program to implement // the above approach using System;using System.Collections.Generic;class GFG{// Function to find the largest element // of the longest subarray consisting // only of odd or even elements only static int maxelementLongestSub(int[] arr, int n){ // Stores largest element of the // longest subarray till i-th index int MaxElem = arr[0]; // Stores maximum length of the // longest subarray till i-th index int maxLen = 1; // Stores length of the current // subarray including the i-th element int Len = 1; // Stores largest element in // current subarray int Max = arr[0]; // Traverse the array for(int i = 1; i < n; i++) { // If arr[i] and arr[i - 1] // are either even numbers // or odd numbers if (arr[i] % 2 == arr[i - 1] % 2) { // Update Len Len++; // Update Max if (arr[i] > Max) Max = arr[i]; // If Len greater than // maxLen if (Len >= maxLen) { maxLen = Len; // Update MaxElem if (Max >= MaxElem) MaxElem = Max; } } else { // Update Len Len = 1; // Update Max Max = arr[i]; // If Len greater // than maxLen if (Len >= maxLen) { // Update maxLen maxLen = Len; // If Max greater // than MaxElem if (Max >= MaxElem) { // Update MaxElem MaxElem = Max; } } } } return MaxElem;}// Driver Codepublic static void Main(String[] args){ int[] arr = { 1, 3, 5, 7, 8, 12, 10 }; int n = arr.Length; // Function call Console.Write(maxelementLongestSub(arr, n));}}// This code is contributed by sourav singh |
Javascript
<script> // JavaScript program to implement // the above approach // Function to find the largest element // of the longest subarray consisting // only of odd or even elements only function maxelementLongestSub(arr, n) { // Stores largest element of the // longest subarray till i-th index var MaxElem = arr[0]; // Stores maximum length of the // longest subarray till i-th index var maxLen = 1; // Stores length of the current // subarray including the i-th element var Len = 1; // Stores largest element in // current subarray var Max = arr[0]; // Traverse the array for (var i = 1; i < n; i++) { // If arr[i] and arr[i - 1] // are either even numbers // or odd numbers if (arr[i] % 2 == arr[i - 1] % 2) { // Update Len Len++; // Update Max if (arr[i] > Max) Max = arr[i]; // If Len greater than // maxLen if (Len >= maxLen) { maxLen = Len; // Update MaxElem if (Max >= MaxElem) MaxElem = Max; } } else { // Update Len Len = 1; // Update Max Max = arr[i]; // If Len greater // than maxLen if (Len >= maxLen) { // Update maxLen maxLen = Len; // If Max greater // than MaxElem if (Max >= MaxElem) { // Update MaxElem MaxElem = Max; } } } } return MaxElem; } // Driver Code var arr = [1, 3, 5, 7, 8, 12, 10]; var n = arr.length; document.write(maxelementLongestSub(arr, n)); </script> |
Output
7
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!
