Check if the array can be split into subarrays such that the XOR of the length of the Longest Decreasing Subsequences of those subarrays is 0

Implementation in C++

// C++ code to Check if the array can be split into subarrays such that the XOR of the length of the Longest Decreasing Subsequences of those subarrays is 0
#include <bits/stdc++.h>
using namespace std;

// function to find xor of longest decreasing subsequence
void xor_of_longest_decreasing_subsequence(int arr[], int n)
{
    // if the length is even, the answer is always 0
    // because each element can be considered
    // as an lds and then all even 1s will give 0

    if (n % 2 == 0)
    {
        cout << "YES" << endl;
        return;
    }
    else
    {
        // for the odd length, we will find any
        // subarray of length 2, which is increasing
        // because then LDS will be 1 and the xor of
        // all the n-1 lds of length 1 would be zero

        bool flag = false;
        for (int i = 1; i < n; i++)
        {

            // Check if there are 2
            // consecutive increasing elements
            if (arr[i] > arr[i - 1])
            {
                flag = true;
                break;
            }
        }
        if (flag)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
}

// Driver Code for the problem to check if the array can be split into subarrays such that the XOR of the length of the Longest Decreasing Subsequences of those subarrays is 0
int main()
{
    // Initializing array of arr
    int arr[] = {5, 4, 3, 2, 1};
    int N = sizeof(arr) / sizeof(arr[0]);

    // Call the function
    xor_of_longest_decreasing_subsequence(arr, N);

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input: 

N = 5 
arr[] = {5, 4, 3, 2, 1}

Output:

NO

Complexity Analysis

Time Complexity: O(N)

Since we are doing single traversal, the time complexity is O(N).

Space Complexity: O(1)

Since we are not using extra space to compute our answer, the space complexity will be O(1).

Check out this problem - Search In Rotated Sorted Array

Frequently asked questions

Q1. What is XOR operation?

Ans- XOR is a boolean logic operator. There are two inputs, and XOR produces one output.

Q2. What is a Subsequence?

Ans- A subsequence is a sequence that can be derived from a sequence by deleting some elements of that sequence, but the order remains unchanged.

Q3. What is the longest increasing subsequence?

Ans- Longest Increasing Subsequence is the subsequence in which subsequence’s elements are present in ascending order and also the subsequence is the longest possible among every other subsequence.

For example

arr[] = {5, 4, 1, 3, 5, 2, 6}

Here the longest decreasing subsequence is, [1, 3, 5, 6]

Key takeaways:

In this article, we discussed the problem to check if the array can be split into subarrays such that the XOR of the length of the Longest Decreasing Subsequences of those subarrays is 0. We have discussed its approach, and we have also discussed the time and space complexities of the approach.

We hope you have gained some understanding of the problem, and now it is your turn to code this problem.

Recommended Read: 

Array in Python

Until then, Keep Learning and Keep Coding.

Until then, Keep Learning and Keep Coding and Keep practicing on Coding Ninjas Studio.

Try this problem: Maximum Xor Subarray.