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