We are given an array a of size N. The task is to print the length of the longest alternative odd/even or even/odd subsequence.
Examples:
Input: a[] = { 13, 16, 8, 9, 32, 10 }
Output: 4
{13, 16, 9, 10} or any other subsequence of length 4 can be the answer.
Input: a[] = {1, 2, 3, 3, 9}
Output: 3
Approach: The answer to the longest alternative parity subsequence will be either [odd, even, odd, even, …..] or [even, odd, even, odd, ….] sequence. Hence iterate in the array and first find the longest odd/even subsequence, and then the most extended even/odd sequence. The steps to find the longest subsequence is:
- Iterate and find the next odd number and increase the length.
- Iterate and find the next odd number and increase the length.
- Repeat steps 1 and steps 2 alternatively starting from steps 1 till the end to find the longest odd/even subsequence.
- Repeat steps 1 and steps 2 alternatively starting from steps 2 till the end to find the longest even/odd subsequence.
Below is the implementation of the above approach:
C++
// C++ program to find the length// of the longest alternative parity// subsequence#include <iostream>using namespace std;// Function to find the longestint longestAlternativeSequence(int a[], int n){ int maxi1 = 0; // Marks the starting of odd // number as sequence and // alternatively changes int f1 = 0; // Finding the longest odd/even sequence for (int i = 0; i < n; i++) { // Find odd number if (!f1) { if (a[i] % 2) { f1 = 1; maxi1++; } } // Find even number else { if (a[i] % 2 == 0) { maxi1++; f1 = 0; } } } int maxi2 = 0; int f2 = 0; // Length of the longest even/odd sequence for (int i = 0; i < n; i++) { // Find odd number if (f2) { if (a[i] % 2) { f2 = 1; maxi2++; } } // Find even number else { if (a[i] % 2 == 0) { maxi2++; f2 = 0; } } } // Answer is maximum of both // odd/even or even/odd subsequence return max(maxi1, maxi2);}// Driver Codeint main(){ int a[] = { 13, 16, 8, 9, 32, 10 }; int n = sizeof(a) / sizeof(a[0]); cout << longestAlternativeSequence(a, n);} |
Java
// Java program to find the length// of the longest alternative parity// subsequenceclass GFG {// Function to find the longeststatic int longestAlternativeSequence(int a[], int n){ int maxi1 = 0; // Marks the starting of odd // number as sequence and // alternatively changes int f1 = 0; // Finding the longest odd/even sequence for (int i = 0; i < n; i++) { // Find odd number if (f1 % 2 != 0) { if (a[i] % 2 == 1) { f1 = 1; maxi1++; } } // Find even number else { if (a[i] % 2 == 0) { maxi1++; f1 = 0; } } } int maxi2 = 0; int f2 = 0; // Length of the longest even/odd sequence for (int i = 0; i < n; i++) { // Find odd number if (f2 % 2 != 0) { if (a[i] % 2 == 1) { f2 = 1; maxi2++; } } // Find even number else { if (a[i] % 2 == 0) { maxi2++; f2 = 0; } } } // Answer is maximum of both // odd/even or even/odd subsequence return Math.max(maxi1, maxi2);}// Driver Codepublic static void main(String[] args) { int a[] = { 13, 16, 8, 9, 32, 10 }; int n = a.length; System.out.println(longestAlternativeSequence(a, n));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to find the length# of the longest alternative parity# subsequence# Function to find the longestdef longestAlternativeSequence(a, n): maxi1 = 0 # Marks the starting of odd # number as sequence and # alternatively changes f1 = 0 # Finding the longest odd/even sequence for i in range(n): # Find odd number if (f1 == 0): if (a[i] % 2): f1 = 1 maxi1 += 1 # Find even number else: if (a[i] % 2 == 0): maxi1 += 1 f1 = 0 maxi2 = 0 f2 = 0 # Length of the longest even/odd sequence for i in range(n): # Find odd number if (f2): if (a[i] % 2): f2 = 1 maxi2 += 1 # Find even number else: if (a[i] % 2 == 0): maxi2 += 1 f2 = 0 # Answer is maximum of both # odd/even or even/odd subsequence return max(maxi1, maxi2)# Driver Codea = [13, 16, 8, 9, 32, 10]n = len(a)print(longestAlternativeSequence(a, n))# This code is contributed by Mohit Kumar |
C#
// C# program to find the length// of the longest alternative parity// subsequenceusing System;class GFG{ // Function to find the longeststatic int longestAlternativeSequence(int []a, int n){ int maxi1 = 0; // Marks the starting of odd // number as sequence and // alternatively changes int f1 = 0; // Finding the longest odd/even sequence for (int i = 0; i < n; i++) { // Find odd number if (f1 != 0) { if (a[i] % 2 == 0) { f1 = 1; maxi1++; } } // Find even number else { if (a[i] % 2 == 0) { maxi1++; f1 = 0; } } } int maxi2 = 0; int f2 = 0; // Length of the longest even/odd sequence for (int i = 0; i < n; i++) { // Find odd number if (f2 == 0) { if (a[i] % 2 == 0) { f2 = 1; maxi2++; } } // Find even number else { if (a[i] % 2 == 0) { maxi2++; f2 = 0; } } } // Answer is maximum of both // odd/even or even/odd subsequence return Math.Max(maxi1, maxi2);}// Driver Codepublic static void Main(){ int []a = { 13, 16, 8, 9, 32, 10 }; int n = a.Length; Console.Write(longestAlternativeSequence(a, n));}}// This code is contributed by Nidhi |
Javascript
<script>// Javascript program to find the length// of the longest alternative parity// subsequence// Function to find the longestfunction longestAlternativeSequence(a, n){ let maxi1 = 0; // Marks the starting of odd // number as sequence and // alternatively changes let f1 = 0; // Finding the longest odd/even sequence for (let i = 0; i < n; i++) { // Find odd number if (!f1) { if (a[i] % 2) { f1 = 1; maxi1++; } } // Find even number else { if (a[i] % 2 == 0) { maxi1++; f1 = 0; } } } let maxi2 = 0; let f2 = 0; // Length of the longest even/odd sequence for (let i = 0; i < n; i++) { // Find odd number if (f2) { if (a[i] % 2) { f2 = 1; maxi2++; } } // Find even number else { if (a[i] % 2 == 0) { maxi2++; f2 = 0; } } } // Answer is maximum of both // odd/even or even/odd subsequence return Math.max(maxi1, maxi2);}// Driver Code let a = [ 13, 16, 8, 9, 32, 10 ]; let n = a.length; document.write(longestAlternativeSequence(a, n));</script> |
Output
4
Time complexity – O(n), since there runs a loop from 0 to (n – 1).
Auxiliary Space – O(1), since no extra space has been taken.
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!
