Количество троек в массиве, имеющем подмассив xor, равный

Опубликовано: 12 Января, 2022

Учитывая массив целых чисел Arr . Задача состоит в том, чтобы подсчитать количество троек (i, j, k) таких, что A _i ^ A _{i + 1} ^ A _{i + 2} ^…. ^ A _j-1 = A _j ^ A _{j + 1} ^ A _{j + 2} ^… .. ^ A _k , и 0 ≤i <j≤ k <N , где N - размер массива.
Где ^ - это побитовый xor двух чисел.

Примеры:

Input: Arr = {5, 2, 7}
Output: 2
The triplets are (0, 2, 2) since 5 ^ 2 = 7 and (0, 1, 2) since 2 ^ 7 = 5.
Input: Arr = {1, 2, 3, 4, 5}
Output: 5

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход грубой силы: простое решение - запустить три вложенных цикла, повторяющих все возможные значения i , j и k, а затем еще один цикл для вычисления xor как первого, так и второго подмассива.
Временная сложность этого решения составляет O (N ⁴ ) .

Эффективный подход:

Эффективное решение - использовать Trie.
Одно наблюдение состоит в том, что если подмассив от i до k имеет A _i ^ A _{i + 1} ^…. ^ A _k = 0, тогда мы можем выбрать любое j такое, что i <j <= k, и это всегда будет удовлетворять нашему условию.
Это наблюдение будет использовано для расчета количества троек.
Мы возьмем кумулятивный xor элементов в массиве и проверим, существует ли это значение xor в Trie или нет.
1. Если xor уже существует в Trie, то мы включили подмассив, имеющий 0 xor, и подсчитали все триплеты.
2. В противном случае поместите значение xor в Trie .

Below is the implementation of the above approach:

C++

// C++ trie based program to find the Number of
// triplets in array having subarray xor equal
#include <bits/stdc++.h>
using namespace std;
 
// maximum number of bits
// in an integer <= 1e9
#define lg 31
 
// Structure of a Trie Node
struct TrieNode {
 
    // [0] index is bit 0
    // and [1] index is bit 1
    TrieNode* children[2];
 
    // Sum of indexes
    // inserted at at a node
    int sum_of_indexes;
 
    // Number of indexes
    // inserted at a node
    int number_of_indexes;
 
    // Constructor to initialize
    // a newly created node
    TrieNode()
    {
 
        this->children[0] = nullptr;
        this->children[1] = nullptr;
        this->sum_of_indexes = 0;
        this->number_of_indexes = 0;
    }
};
 
// Function to insert curr_xor
// into the trie
void insert(TrieNode* node,
            int num,
            int index)
{
 
    // Iterate from the 31st bit
    // to the 0th bit of curr_xor
    // number
    for (int bits = lg; bits >= 0; bits--) {
 
        // Check if the current
        // bit is set or not
        int curr_bit = (num >> bits) & 1;
 
        // If this node isn"t already
        // present in the trie structure
        // insert it into the trie.
        if (node->children[curr_bit]
            == nullptr) {
            node->children[curr_bit]
                = new TrieNode();
        }
 
        node = node->children[curr_bit];
    }
 
    // Increase the sum of
    // indexes by the current
    // index value
    node->sum_of_indexes += index;
 
    // Increase the number
    // of indexes by 1
    node->number_of_indexes++;
}
 
// Function to check if curr_xor
// is present in trie or not
int query(TrieNode* node,
          int num,
          int index)
{
 
    // Iterate from the 31st bit
    // to the 0th bit of curr_xor number
    for (int bits = lg; bits >= 0; bits--) {
 
        // Check if the current bit
        // is set or not
        int curr_bit = (num >> bits) & 1;
 
        // If this node isn"t already
        // present in the trie structure
        // that means no sub array till
        // current index has 0 xor so
        // return 0
        if (node->children[curr_bit]
            == nullptr) {
            return 0;
        }
 
        node = node->children[curr_bit];
    }
 
    // Calculate the number of index
    // inserted at final node
    int sz = node->number_of_indexes;
 
    // Calculate the sum of index
    // inserted at final node
    int sum = node->sum_of_indexes;
 
    int ans = (sz * index) - (sum);
 
    return ans;
}
 
// Function to return the count of
// valid triplets
int no_of_triplets(int arr[], int n)
{
 
    // To store cumulative xor
    int curr_xor = 0;
 
    int number_of_triplets = 0;
 
    // The root of the trie
    TrieNode* root = new TrieNode();
 
    for (int i = 0; i < n; i++) {
 
        int x = arr[i];
 
        // Insert the curr_xor in the trie
        insert(root, curr_xor, i);
 
        // Update the cumulative xor
        curr_xor ^= x;
 
        // Check if the cumulative xor
        // is present in the trie or not
        // if present then add
        // (sz * index) - sum
        number_of_triplets
            += query(root, curr_xor, i);
    }
 
    return number_of_triplets;
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 5, 2, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << no_of_triplets(arr, n);
 
    return 0;
}

Java

// Java trie based program to find the Number of
// triplets in array having subarray xor equal
class GFG
{
     
// maximum number of bits
// in an integer <= 1e9
static int lg = 31;
 
// Structure of a Trie Node
static class TrieNode
{
 
    // [0] index is bit 0
    // and [1] index is bit 1
    TrieNode children[];
 
    // Sum of indexes
    // inserted at at a node
    int sum_of_indexes;
 
    // Number of indexes
    // inserted at a node
    int number_of_indexes;
 
    // Constructor to initialize
    // a newly created node
    TrieNode()
    {
        children = new TrieNode[2];
        this.children[0] = null;
        this.children[1] = null;
        this.sum_of_indexes = 0;
        this.number_of_indexes = 0;
    }
};
 
// Function to insert curr_xor
// into the trie
static void insert(TrieNode node,
                    int num,
                    int index)
{
 
    // Iterate from the 31st bit
    // to the 0th bit of curr_xor
    // number
    for (int bits = lg; bits >= 0; bits--)
    {
 
        // Check if the current
        // bit is set or not
        int curr_bit = (num >> bits) & 1;
 
        // If this node isn"t already
        // present in the trie structure
        // insert it into the trie.
        if (node.children[curr_bit]
            == null)
        {
            node.children[curr_bit]
                = new TrieNode();
        }
 
        node = node.children[curr_bit];
    }
 
    // Increase the sum of
    // indexes by the current
    // index value
    node.sum_of_indexes += index;
 
    // Increase the number
    // of indexes by 1
    node.number_of_indexes++;
}
 
// Function to check if curr_xor
// is present in trie or not
static int query(TrieNode node,
                  int num,
                  int index)
{
 
    // Iterate from the 31st bit
    // to the 0th bit of curr_xor number
    for (int bits = lg; bits >= 0; bits--)
    {
 
        // Check if the current bit
        // is set or not
        int curr_bit = (num >> bits) & 1;
 
        // If this node isn"t already
        // present in the trie structure
        // that means no sub array till
        // current index has 0 xor so
        // return 0
        if (node.children[curr_bit]
            == null)
        {
            return 0;
        }
 
        node = node.children[curr_bit];
    }
 
    // Calculate the number of index
    // inserted at final node
    int sz = node.number_of_indexes;
 
    // Calculate the sum of index
    // inserted at final node
    int sum = node.sum_of_indexes;
 
    int ans = (sz * index) - (sum);
 
    return ans;
}
 
// Function to return the count of
// valid triplets
static int no_of_triplets(int arr[], int n)
{
 
    // To store cumulative xor
    int curr_xor = 0;
 
    int number_of_triplets = 0;
 
    // The root of the trie
    TrieNode root = new TrieNode();
 
    for (int i = 0; i < n; i++)
    {
 
        int x = arr[i];
 
        // Insert the curr_xor in the trie
        insert(root, curr_xor, i);
 
        // Update the cumulative xor
        curr_xor ^= x;
 
        // Check if the cumulative xor
        // is present in the trie or not
        // if present then add
        // (sz * index) - sum
        number_of_triplets
            += query(root, curr_xor, i);
    }
 
    return number_of_triplets;
}
 
// Driver Code
public static void main(String args[])
{
    // Given array
    int arr[] = { 5, 2, 7 };
    int n = arr.length;
 
    System.out.println(no_of_triplets(arr, n));
}
}
 
// This code is contributed by Arnab Kundu

Output

Временная сложность: O (31 * N)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Структуры данных

Количество троек в массиве, имеющем подмассив xor, равный

C++

Java

РЕКОМЕНДУЕМЫЕ СТАТЬИ