Given an array of integers arr[] of size N, the task is to check whether arr[] can be split into different subarrays such that on taking the XOR of lengths of LDS (Longest decreasing subsequences) of all the subarrays is equal to 0. Print ‘YES‘ if it is possible to split else print ‘NO‘.
Examples:
Input: arr[] = {1, 0, 3, 4, 5}
Output: YES
Explanation: {1}, {0}, {3}, {4, 5} length of LDS of subarrays: 1, 1, 1, 1, XOR of lengths = 0. So answer is Yes.Input: arr[] = {5, 4, 3}
Output: NO
Approach: The XOR operation of even number of 1’s is 0. So if the array length is even then each element can be considered as LDS of size 1 which makes XOR of even 1’s equal to 0 and for odd length arrays to have even LDS’s with 1’s any subarray of size 2 can be considered with LDS i.e. the subarray should be strictly increasing so the LDS will be 1. Follow the steps below to solve the problem:
- Initialize a variable found as false.
- If N is even print ‘YES’ and return.
- Else, Iterate over the range (0, N – 1] using the variable i and perform the following tasks:
- Check if there is consecutive increasing elements by arr[i]>arr[i-1]
- If arr[i]>arr[i-1] make found as true and come out of the loop
- If found is true print “YES”, else print “NO”
Below is the implementation of the above approach.
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to find XOR of LDS's// of subarraysvoid xor_of_lds(int arr[], int n){ // If length is even each element // can be considered as lds of length // 1 which makes even 1's and xor is 0 if (n % 2 == 0) { cout << "YES" << endl; return; } else { // For odd length we need to find // even subarray of length 2 which // is strictly increasing so that it // makes a subarray with lds=1 bool found = 0; for (int i = 1; i < n; i++) { // Check if there are 2 // consecutive increasing elements if (arr[i] > arr[i - 1]) { found = 1; break; } } if (found == 1) cout << "YES" << endl; else cout << "NO" << endl; }}// Driver Codeint main(){ // Initializing array of arr int arr[] = { 1, 0, 3, 4, 5 }; int N = sizeof(arr) / sizeof(arr[0]); // Call the function xor_of_lds(arr, N); return 0;} |
Java
// Java code for the above approachimport java.util.*;class GFG{// Function to find XOR of LDS's// of subarraysstatic void xor_of_lds(int arr[], int n){ // If length is even each element // can be considered as lds of length // 1 which makes even 1's and xor is 0 if (n % 2 == 0) { System.out.print("YES" +"\n"); return; } else { // For odd length we need to find // even subarray of length 2 which // is strictly increasing so that it // makes a subarray with lds=1 boolean found = false; for (int i = 1; i < n; i++) { // Check if there are 2 // consecutive increasing elements if (arr[i] > arr[i - 1]) { found = true; break; } } if (found == true) System.out.print("YES" +"\n"); else System.out.print("NO" +"\n"); }}// Driver Codepublic static void main(String[] args){ // Initializing array of arr int arr[] = { 1, 0, 3, 4, 5 }; int N = arr.length; // Call the function xor_of_lds(arr, N);}}// This code is contributed by shikhasingrajput |
Python3
# Python code for the above approach# Function to find XOR of LDS's# of subarraysdef xor_of_lds (arr, n) : # If length is even each element # can be considered as lds of length # 1 which makes even 1's and xor is 0 if (n % 2 == 0): print("YES") return else: # For odd length we need to find # even subarray of length 2 which # is strictly increasing so that it # makes a subarray with lds=1 found = 0 for i in range(1, n): # Check if there are 2 # consecutive increasing elements if (arr[i] > arr[i - 1]): found = 1 break if (found == 1): print("YES") else: print("NO")# Driver Code# Initializing array of arrarr = [1, 0, 3, 4, 5]N = len(arr)# Call the functionxor_of_lds(arr, N)# This code is contributed by Saurabh Jaiswal |
C#
// C# code for the above approachusing System;class GFG{ // Function to find XOR of LDS's// of subarraysstatic void xor_of_lds(int []arr, int n){ // If length is even each element // can be considered as lds of length // 1 which makes even 1's and xor is 0 if (n % 2 == 0) { Console.Write("YES" + "\n"); return; } else { // For odd length we need to find // even subarray of length 2 which // is strictly increasing so that it // makes a subarray with lds=1 bool found = false; for (int i = 1; i < n; i++) { // Check if there are 2 // consecutive increasing elements if (arr[i] > arr[i - 1]) { found = true; break; } } if (found == true) Console.Write("YES" +"\n"); else Console.Write("NO" +"\n"); }}// Driver Codepublic static void Main(){ // Initializing array of arr int []arr = { 1, 0, 3, 4, 5 }; int N = arr.Length; // Call the function xor_of_lds(arr, N);}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find XOR of LDS's // of subarrays const xor_of_lds = (arr, n) => { // If length is even each element // can be considered as lds of length // 1 which makes even 1's and xor is 0 if (n % 2 == 0) { document.write("YES<br/>"); return; } else { // For odd length we need to find // even subarray of length 2 which // is strictly increasing so that it // makes a subarray with lds=1 let found = 0; for (let i = 1; i < n; i++) { // Check if there are 2 // consecutive increasing elements if (arr[i] > arr[i - 1]) { found = 1; break; } } if (found == 1) document.write("YES<br/>"); else document.write("NO<br/>"); } } // Driver Code // Initializing array of arr let arr = [1, 0, 3, 4, 5]; let N = arr.length; // Call the function xor_of_lds(arr, N); // This code is contributed by rakeshsahni</script> |
Output
YES
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
