## Introduction

This blog will discuss the solution to this 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. Longest Decreasing Subsequence is the subsequence in which subsequenceâ€™s elements are present in descending order and also the subsequence is the longest possible among every other subsequence.

Recommended topic, __kth largest element in an array__ and __Euclid GCD Algorithm__

### Problem Statement

We are given an array arr[] of size N; our task is to find arr[] that can be split into different subarrays such that after taking XOR of lengths of Longest Decreasing Subsequence of all the subarrays, it is equal to 0. If equal to 0, then we will print â€śYESâ€ť Else we will print â€śNOâ€ť, So before we deep dive into the answer, we should look at some examples to understand the problem better.

**Example:**

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

Here the longest decreasing subsequence is, [5, 2, 1, 4].

Let us have a look at few more examples to get a clear understanding of the problem.

### Sample Examples

**Example 1:**

```
Input:
arr[] = {4, 2, 3, 1}
Output:
YES
Explanation:
Lds subsequences = [4], [2], [3], [1]
Lds array[] = {1,1,1,1}
Xor of all elements of this LDS array is zero.
```

**Example 2:**

```
Input:
arr[] = {7, 2, 1, 4, 3}
Output:
YES
Explanation:
Lds subsequences = [7], [2, 1], [4], [3]
Lds array[] = {1, 1, 1, 1}
Xor of all the elements of this LDS array is zero.
```

## Approach

To solve this 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 know that the XOR operation of an even number of 1s is zero. So if the length of the array is even, then we can consider every element as LDS of size 1; therefore, the even-sized array will always answer to zero. Now, if the size of the array is odd, we will search for any subarray whose length is 2, and we find any such subarray, its LDS would be 1. So there would be (n-1) 1s, and since n is odd, so n-1 would be even, then the XOR would be equal to zero.

### Steps of algorithm

- If N is even, then print â€śYESâ€ť and return.
- Else we will initialize a flag variable with value false.
- We will traverse in a loop from [0, N-1) and if(arr[i] < arr[i+1]) then we would initialize flag value with true.
- If the flag is true, then we will print â€śYESâ€ť. Else, we would print â€śNOâ€ť.