Subarreglo con XOR menor que k

Posted on by Rudeus Greyrat

Dada una array de n números y un número k. Tienes que escribir un programa para encontrar el número de subarreglos con x o menos que k.

Ejemplos: 

Entrada:  arr[] = {8, 9, 10, 11, 12}, k=3
Salida: 4
Explicación: Sub-arrays [1:3], [2:3], [2:5], [4: 5] tienen valores xor 2, 1, 0, 1 respectivamente.

Entrada: arr[] = {12, 4, 6, 8, 21}, k=8
Salida: 4

Enfoque ingenuo: el algoritmo ingenuo es simplemente calcular el valor xor de todos y cada uno de los subarreglos y compararlo con el número k dado para encontrar la respuesta. 

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

C++

// C++ program to count number of
// subarrays with XOR less than k
#include <iostream>
using namespace std;
 
// function to count number of
// subarrays with XOR less than k
int xorLessK(int arr[], int n, int k)
{
    int count = 0;
 
    // check all subarrays
    for (int i = 0; i < n; i++) {
        int tempXor = 0;
        for (int j = i; j < n; j++) {
            tempXor ^= arr[j];
            if (tempXor < k)
                count++;
        }
    }
 
    return count;
}
 
// Driver program to test above function
int main()
{
    int n, k = 3;
    int arr[] = { 8, 9, 10, 11, 12 };
 
    n = sizeof(arr) / sizeof(arr[0]);
 
    cout << xorLessK(arr, n, k);
 
    return 0;
}

Java

// Java program to count number of
// subarrays with XOR less than k
 
import java.io.*;
 
class GFG {
     
// function to count number of
// subarrays with XOR less than k
static int xorLessK(int arr[], int n, int k)
{
    int count = 0;
 
    // check all subarrays
    for (int i = 0; i < n; i++) {
        int tempXor = 0;
        for (int j = i; j < n; j++) {
            tempXor ^= arr[j];
            if (tempXor < k)
                count++;
        }
    }
 
    return count;
}
 
// Driver program to test above function
    public static void main (String[] args) {
 
         
    int k = 3;
    int arr[] = new int[] { 8, 9, 10, 11, 12 };
    int n = arr.length;
 
    System.out.println(xorLessK(arr, n, k));
         
    }
}

Python3

# Python 3 program to count number of
# subarrays with XOR less than k
 
# function to count number of
# subarrays with XOR less than k
def xorLessK(arr, n, k):
    count = 0
 
    # check all subarrays
    for i in range(n):
        tempXor = 0
        for j in range(i, n):
            tempXor ^= arr[j]
            if (tempXor < k):
                count += 1
     
    return count
 
# Driver Code
if __name__ == '__main__':
    k = 3
    arr = [8, 9, 10, 11, 12]
 
    n = len(arr)
 
    print(xorLessK(arr, n, k))
 
# This code is contributed by
# Sahil_shelangia

C#

// C# program to count number of
// subarrays with XOR less than k
using System;
 
class GFG {
     
// function to count number of
// subarrays with XOR less than k
static int xorLessK(int []arr, int n, int k)
{
    int count = 0;
 
    // check all subarrays
    for (int i = 0; i < n; i++) {
         
        int tempXor = 0;
         
        for (int j = i; j < n; j++) {
             
            tempXor ^= arr[j];
            if (tempXor < k)
                count++;
        }
    }
 
    return count;
}
 
// Driver Code
static public void Main ()
{
         
    int k = 3;
    int []arr = new int[] {8, 9, 10,
                           11, 12 };
    int n = arr.Length;
    Console.WriteLine(xorLessK(arr, n, k));
     
}
}

PHP

<?php
// PHP program to count number of
// subarrays with XOR less than k
 
// function to count number of
// subarrays with XOR less than k
function xorLessK($arr, $n, $k)
{
    $count = 0;
 
    // check all subarrays
    for ($i = 0; $i < $n; $i++)
    {
        $tempXor = 0;
        for ($j = $i; $j < $n; $j++)
        {
            $tempXor ^= $arr[$j];
            if ($tempXor < $k)
                $count++;
        }
    }
 
    return $count;
}
 
    // Driver Code
    $n; $k = 3;
    $arr = array(8, 9, 10, 11, 12);
 
    $n = count($arr);
 
    echo xorLessK($arr, $n, $k);
 
// This code is contributed by anuj_67.
?>

Javascript

<script>
    // Javascript program to count number of
    // subarrays with XOR less than k
     
    // function to count number of
    // subarrays with XOR less than k
    function xorLessK(arr, n, k)
    {
        let count = 0;
 
        // check all subarrays
        for (let i = 0; i < n; i++) {
 
            let tempXor = 0;
 
            for (let j = i; j < n; j++) {
 
                tempXor ^= arr[j];
                if (tempXor < k)
                    count++;
            }
        }
 
        return count;
    }
     
    let k = 3;
    let arr = [8, 9, 10, 11, 12];
    let n = arr.length;
    document.write(xorLessK(arr, n, k));
     
</script>
Producción

3

Complejidad del tiempo :  O(n^2) . 

Enfoque eficiente: un enfoque eficiente será calcular todos los valores de xor del prefijo, es decir, a[1:i] para todos los i. 
Se puede verificar que el xor de un subarreglo a[l:r] se puede escribir como (a[1:l-1] xor a[1:r]), donde a[i, j] es el xor de todos los elementos con índice tal que, i <= índice <= j. 

Explicación: 
Almacenaremos un número como un número binario en trie. El hijo de la izquierda mostrará que el siguiente bit es 0 y el hijo de la derecha mostrará que el siguiente bit es 1. 
Por ejemplo, la siguiente imagen muestra los números 1001 y 1010 en trie. 
 

trie1

Si xor[i, j] representa el xor de todos los elementos en el subarreglo a[i, j], entonces en un índice i lo que tenemos es un trie que tiene xor[1:1], xor[1:2] …..xor[1:i-1] ya insertado. Ahora de alguna manera contamos cuántos de estos (números en trie) son tales que su xor con xor[1:i] es menor que k. Esto cubrirá todos los subarreglos que terminen en el índice i y que tengan xor, es decir, xor[j, i] <=k;
Ahora queda el problema, cómo contar los números con x o más pequeños que k. Entonces, por ejemplo, tome el bit actual del i-ésimo elemento de índice como p, un bit actual del número k como q y el Node actual en trie como Node. 

Tomemos el caso cuando p=1, k=1. Entonces, si vamos al hijo de la derecha, el xor actual sería 0 (ya que el hijo de la derecha significa 1 y p=1, 1(xor)1=0). Como k=1, todos los números que están al hijo de la derecha de este Node daría un valor de xor menor que k. Entonces, contaríamos los números que están justo en este Node. 
Si vamos al hijo izquierdo, el xor actual sería 1 (ya que el hijo izquierdo significa 0 y p=1, 0(xor)1=1). Entonces, si vamos al hijo de la izquierda, aún podemos encontrar un número con xor más pequeño que k, por lo tanto, pasamos al hijo de la izquierda.

Entonces, para contar los números que están debajo de un Node dado, modificamos el trie y cada Node también almacenará el número de hojas en ese subárbol y esto se modificaría después de cada inserción.

Otros tres casos para diferentes valores de p y k se pueden resolver de la misma manera para contar el número de números con x o menos que k.

A continuación se muestra la implementación en C++ de la idea anterior: 

CPP

#include <iostream>
using namespace std;
class trienode {
public:
    int left_count, right_count;
    trienode* left;
    trienode* right;
    trienode()
    {
        left_count = 0;
        right_count = 0;
 
        // Left denotes 0
        left = NULL;
 
        // Right denotes 1
        right = NULL;
    }
};
void insert(trienode* root, int element)
{
    for (int i = 31; i >= 0; i--) {
        int x = (element >> i) & 1;
 
        // If the current bit is 1
        if (x) {
            root->right_count++;
            if (root->right == NULL)
                root->right = new trienode();
            root = root->right;
        }
        else {
            root->left_count++;
            if (root->left == NULL)
                root->left = new trienode();
            root = root->left;
        }
    }
}
int query(trienode* root, int element, int k)
{
    if (root == NULL)
        return 0;
    int res = 0;
    for (int i = 31; i >= 0; i--) {
        bool current_bit_of_k = (k >> i) & 1;
        bool current_bit_of_element = (element >> i) & 1;
 
        // If the current bit of k is 1
        if (current_bit_of_k) {
            // If current bit of element is 1
            if (current_bit_of_element) {
                res += root->right_count;
                if (root->left == NULL)
                    return res;
                root = root->left;
            }
 
            // If current bit of element is 0
            else {
                res += root->left_count;
                if (root->right == NULL)
                    return res;
                root = root->right;
            }
        }
 
        // If the current bit of k is zero
        else {
            // If current bit of element is 1
            if (current_bit_of_element) {
                if (root->right == NULL)
                    return res;
                root = root->right;
            }
 
            // If current bit of element is 0
            else {
                if (root->left == NULL)
                    return res;
                root = root->left;
            }
        }
    }
    return res;
}
 
// Driver code
int main()
{
 
    int n = 5, k = 3;
    int arr[] = { 8, 9, 10, 11, 12 };
 
    // Below three variables are used for storing
    // current XOR
    int temp, temp1, temp2 = 0;
    trienode* root = new trienode();
    insert(root, 0);
    long long total = 0;
    for (int i = 0; i < n; i++) {
        temp = arr[i];
        temp1 = temp2 ^ temp;
        total += query(root, temp1, k);
        insert(root, temp1);
        temp2 = temp1;
    }
 
    cout << total << endl;
 
    return 0;
}
Producción

3

Complejidad de tiempo: O(n*log(max)), donde max es el elemento máximo en la array.
Artículos relacionados : 

Este artículo es una contribución de Amritya Vagmi . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 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 *