Longest alternative parity subsequence

0 0 5 minutes read

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 longest
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) {
            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 Code
int 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
// subsequence
class GFG 
{
 
// Function to find the longest
static 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 Code
public 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 longest
def 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 Code
a = [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
// subsequence
using System;
 
class GFG
{
     
// Function to find the longest
static 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 Code
public 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 longest
function 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

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 zambiatek!