Subarreglo más largo con XOR estrictamente positivo

Dada una array arr[] de N enteros no negativos. La tarea es encontrar la longitud del subarreglo más largo tal que el XOR de todos los elementos de este subarreglo sea estrictamente positivo. Si no existe tal subarreglo, imprima -1
Ejemplos:

Entrada: arr[] = {1, 1, 1, 1}
Salida: 3
Tomar sub-arreglo[0:2] = {1, 1, 1}
Xor de este subarreglo es igual a 1.
Entrada: arr[ ] = {0, 1, 5, 19}
Salida: 4

Acercarse:

Si el XOR de la array completa es positivo , entonces la respuesta es igual a N.
Si todos los elementos son ceros, la respuesta es -1 , ya que es imposible obtener un XOR estrictamente positivo.
De lo contrario, digamos que el índice del primer número positivo es l y el último número positivo es r .
Ahora, el XOR de todos los elementos del rango de índice [l, r] debe ser cero, ya que los elementos antes de l y después de r son 0 , lo que no contribuirá al valor de XOR y el XOR de la array original era 0 .
Considere los subconjuntos A ₁ , A ₁ , …, A _r-1 y A _l+1 , A _l+2 , …, A _N .
El primer subarreglo tendría un valor XOR igual a A[r] y el segundo, tendría un valor XOR A[l] que es positivo.
Devuelve la longitud del subconjunto más grande entre estos dos subconjuntos.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the length of the
// longest sub-array having positive XOR
int StrictlyPositiveXor(int A[], int N)
{
 
    // To store the XOR
    // of all the elements
    int allxor = 0;
 
    // To check if all the
    // elements of the array are 0s
    bool checkallzero = true;
 
    for (int i = 0; i < N; i += 1) {
 
        // Take XOR of all the elements
        allxor ^= A[i];
 
        // If any positive value is found
        // the make the checkallzero false
        if (A[i] > 0)
            checkallzero = false;
    }
 
    // If complete array is the answer
    if (allxor != 0)
        return N;
 
    // If all elements are equal to zero
    if (checkallzero)
        return -1;
 
    // Initialize l and r
    int l = N, r = -1;
 
    for (int i = 0; i < N; i += 1) {
 
        // First positive value of the array
        if (A[i] > 0) {
            l = i + 1;
            break;
        }
    }
    for (int i = N - 1; i >= 0; i -= 1) {
 
        // Last positive value of the array
        if (A[i] > 0) {
            r = i + 1;
            break;
        }
    }
 
    // Maximum length among
    // these two subarrays
    return max(N - l, r - 1);
}
 
// Driver code
int main()
{
 
    int A[] = { 1, 0, 0, 1 };
 
    int N = sizeof(A) / sizeof(A[0]);
 
    cout << StrictlyPositiveXor(A, N);
 
    return 0;
}

Java

// Java implementation of the approach
import java.io.*;
 
class GFG
{
 
// Function to return the length of the
// longest sub-array having positive XOR
static int StrictlyPositiveXor(int []A, int N)
{
 
    // To store the XOR
    // of all the elements
    int allxor = 0;
 
    // To check if all the
    // elements of the array are 0s
    boolean checkallzero = true;
 
    for (int i = 0; i < N; i += 1)
    {
 
        // Take XOR of all the elements
        allxor ^= A[i];
 
        // If any positive value is found
        // the make the checkallzero false
        if (A[i] > 0)
            checkallzero = false;
    }
 
    // If complete array is the answer
    if (allxor != 0)
        return N;
 
    // If all elements are equal to zero
    if (checkallzero)
        return -1;
 
    // Initialize l and r
    int l = N, r = -1;
 
    for (int i = 0; i < N; i += 1)
    {
 
        // First positive value of the array
        if (A[i] > 0)
        {
            l = i + 1;
            break;
        }
    }
    for (int i = N - 1; i >= 0; i -= 1)
    {
 
        // Last positive value of the array
        if (A[i] > 0)
        {
            r = i + 1;
            break;
        }
    }
 
    // Maximum length among
    // these two subarrays
    return Math.max(N - l, r - 1);
}
 
// Driver code
public static void main (String[] args)
{
    int A[] = { 1, 0, 0, 1 };
 
    int N = A.length;
 
    System.out.print(StrictlyPositiveXor(A, N));
}
}
 
// This code is contributed by anuj_67..

Python3

# Python3 implementation of the approach
 
# Function to return the length of the
# longest sub-array having positive XOR
def StrictlyPositiveXor(A, N) :
 
    # To store the XOR
    # of all the elements
    allxor = 0;
 
    # To check if all the
    # elements of the array are 0s
    checkallzero = True;
 
    for i in range(N) :
 
        # Take XOR of all the elements
        allxor ^= A[i];
 
        # If any positive value is found
        # the make the checkallzero false
        if (A[i] > 0) :
            checkallzero = False;
 
    # If complete array is the answer
    if (allxor != 0) :
        return N;
 
    # If all elements are equal to zero
    if (checkallzero) :
        return -1;
 
    # Initialize l and r
    l = N; r = -1;
 
    for i in range(N) :
 
        # First positive value of the array
        if (A[i] > 0) :
            l = i + 1;
            break;
             
    for i in range(N - 1, -1, -1) :
 
        # Last positive value of the array
        if (A[i] > 0) :
            r = i + 1;
            break;
 
    # Maximum length among
    # these two subarrays
    return max(N - l, r - 1);
 
 
# Driver code
if __name__ == "__main__" :
 
    A= [ 1, 0, 0, 1 ];
    N = len(A);
    print(StrictlyPositiveXor(A, N));
 
    # This code is contributed by AnkitRai01

C#

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to return the length of the
// longest sub-array having positive XOR
static int StrictlyPositiveXor(int []A, int N)
{
 
    // To store the XOR
    // of all the elements
    int allxor = 0;
 
    // To check if all the
    // elements of the array are 0s
    bool checkallzero = true;
 
    for (int i = 0; i < N; i += 1)
    {
 
        // Take XOR of all the elements
        allxor ^= A[i];
 
        // If any positive value is found
        // the make the checkallzero false
        if (A[i] > 0)
            checkallzero = false;
    }
 
    // If complete array is the answer
    if (allxor != 0)
        return N;
 
    // If all elements are equal to zero
    if (checkallzero)
        return -1;
 
    // Initialize l and r
    int l = N, r = -1;
 
    for (int i = 0; i < N; i += 1)
    {
 
        // First positive value of the array
        if (A[i] > 0)
        {
            l = i + 1;
            break;
        }
    }
    for (int i = N - 1; i >= 0; i -= 1)
    {
 
        // Last positive value of the array
        if (A[i] > 0)
        {
            r = i + 1;
            break;
        }
    }
 
    // Maximum length among
    // these two subarrays
    return Math.Max(N - l, r - 1);
}
 
// Driver code
public static void Main ()
{
    int []A = { 1, 0, 0, 1 };
 
    int N = A.Length;
 
    Console.WriteLine(StrictlyPositiveXor(A, N));
}
}
 
// This code is contributed by anuj_67..

Javascript

<script>
 
// Javascript implementation of the approach
 
// Function to return the length of the
// longest sub-array having positive XOR
function StrictlyPositiveXor(A, N)
{
 
    // To store the XOR
    // of all the elements
    let allxor = 0;
 
    // To check if all the
    // elements of the array are 0s
    let checkallzero = true;
 
    for (let i = 0; i < N; i += 1) {
 
        // Take XOR of all the elements
        allxor ^= A[i];
 
        // If any positive value is found
        // the make the checkallzero false
        if (A[i] > 0)
            checkallzero = false;
    }
 
    // If complete array is the answer
    if (allxor != 0)
        return N;
 
    // If all elements are equal to zero
    if (checkallzero)
        return -1;
 
    // Initialize l and r
    let l = N, r = -1;
 
    for (let i = 0; i < N; i += 1) {
 
        // First positive value of the array
        if (A[i] > 0) {
            l = i + 1;
            break;
        }
    }
    for (let i = N - 1; i >= 0; i -= 1) {
 
        // Last positive value of the array
        if (A[i] > 0) {
            r = i + 1;
            break;
        }
    }
 
    // Maximum length among
    // these two subarrays
    return Math.max(N - l, r - 1);
}
 
// Driver code
 
    let A = [ 1, 0, 0, 1 ];
 
    let N = A.length;
 
    document.write(StrictlyPositiveXor(A, N));
 
</script>

Producción:

Complejidad del tiempo: O(N)

Publicación traducida automáticamente

Artículo escrito por CrazyPro y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta