Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Steps of algorithm
3.
Implementation in C++
3.1.
Complexity Analysis
4.
Frequently asked questions
5.
Key takeaways:
Last Updated: Mar 27, 2024

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

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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

  1. If N is even, then print “YES” and return.
  2. Else we will initialize a flag variable with value false.
  3. 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.
  4. If the flag is true, then we will print “YES”. Else, we would print “NO”.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

 

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.

A

B

A XOR B

0

0

0

0

1

1

0

1

1

1

0

 

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.



 

Previous article
Check if a number is a palindrome or not without using any extra space
Next article
Count Pairs (i, j) From a Given Array Such that ARR[i] > K * ARR[j]
Live masterclass