Compruebe si la array se puede dividir en subarreglos de modo que el XOR de la longitud de las subsecuencias decrecientes más largas de esos subarreglos sea 0

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 ‘ ‘ si es posible dividir, de lo contrario escriba ‘ NO ‘.

Ejemplos:

Entrada: arr[] = {1, 0, 3, 4, 5}
Salida:
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>
Producción

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *