Dada una array de enteros arr[] de tamaño N, la tarea es verificar si arr[] se puede dividir en diferentes subarreglos de modo que al tomar el XOR de longitudes de LDS (subsecuencias decrecientes más largas) de todos los subarreglos sea igual a 0 . Escriba ‘ SÍ ‘ si es posible dividir, de lo contrario escriba ‘ NO ‘.
Ejemplos:
Entrada: arr[] = {1, 0, 3, 4, 5}
Salida: SÍ
Explicación: {1}, {0}, {3}, {4, 5} longitud de LDS de subarreglos: 1, 1, 1 , 1, XOR de longitudes = 0. Entonces la respuesta es Sí.Entrada: arr[] = {5, 4, 3}
Salida: NO
Enfoque: la operación XOR de un número par de 1 es 0. Entonces, si la longitud del arreglo es par, entonces cada elemento puede considerarse como LDS de tamaño 1 , lo que hace que el XOR de los 1 pares sea igual a 0 y que los arreglos de longitud impar tengan LDS pares con Cualquier subarreglo de 1 de tamaño 2 se puede considerar con LDS, es decir, el subarreglo debe aumentar estrictamente para que el LDS sea 1 . Siga los pasos a continuación para resolver el problema:
- Inicializar una variable encontrada como falsa.
- Si N es par, imprima ‘SÍ’ y regrese.
- De lo contrario, itere sobre el rango (0, N – 1] usando la variable i y realice las siguientes tareas:
- Compruebe si hay elementos crecientes consecutivos por arr[i]>arr[i-1]
- Si arr[i]>arr[i-1] hacer encontrado como verdadero y salir del ciclo
- Si es cierto, escriba » SÍ», de lo contrario, escriba «NO»
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find XOR of LDS's
// of subarrays
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) {
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 Code
int 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 approach
import java.util.*;
class GFG{
// Function to find XOR of LDS's
// of subarrays
static 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 Code
public 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 subarrays
def 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 arr
arr = [1, 0, 3, 4, 5]
N = len(arr)
# Call the function
xor_of_lds(arr, N)
# This code is contributed by Saurabh Jaiswal
C#
// C# code for the above approach
using System;
class GFG
{
// Function to find XOR of LDS's
// of subarrays
static 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 Code
public 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>
YES
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA