Рубрики

Количество триплетов, удовлетворяющих данному уравнению

Дан массив arr [] из N неотрицательных целых чисел. Задача состоит в том, чтобы подсчитать количество триплетов (i, j, k), где 0 ≤ i <j ≤ k <N такое, что A [i] ^ A [i + 1] ^… ^ A [j — 1] = A [j] ^ A [j + 1] ^… ^ A [k] где ^ — побитовое значение XOR.

Примеры:

Input: arr[] = {2, 5, 6, 4, 2}
Output: 2
The valid triplets are (2, 3, 4) and (2, 4, 4).

Input: arr[] = {5, 2, 7}
Output: 2

Наивный подход: рассмотрите каждый триплет и проверьте, равен ли xor требуемых элементов или нет.

Эффективный подход: если arr [i] ^ arr [i + 1] ^… ^ arr [j — 1] = arr [j] ^ arr [j + 1] ^… ^ arr [k], то arr [i] ^ arr [i + 1] ^… ^ arr [k] = 0, так как X ^ X = 0 . Теперь проблема сводится к поиску подмассивов с XOR 0. Но у каждого такого подмассива может быть несколько таких триплетов, т.е.

If arr[i] ^ arr[i + 1] ^ … ^ arr[k] = 0
then, (arr[i]) ^ (arr[i + 1] ^ … ^ arr[k]) = 0
and, arr[i] ^ (arr[i + 1]) ^ … ^ arr[k] = 0
arr[i] ^ arr[i + 1] ^ (arr[i + 2]) ^ … ^ arr[k] = 0

j can have any value from i + 1 to k without violating the required property.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для возврата счета
// необходимых триплетов

int CountTriplets(int* arr, int n)

{

    int ans = 0;

    for (int i = 0; i < n - 1; i++) {

  

        // Первый элемент

        // текущий под-массив

        int first = arr[i];

        for (int j = i + 1; j < n; j++) {

  

            // XOR каждый элемент

            // текущий подмассив

            first ^= arr[j];

  

            // Если XOR становится 0, то

            // обновляем количество триплетов

            if (first == 0)

                ans += (j - i);

        }

    }

    return ans;

}

  
// Код драйвера

int main()

{

    int arr[] = { 2, 5, 6, 4, 2 };

    int n = sizeof(arr) / sizeof(arr[0]);

  

    cout << CountTriplets(arr, n);

  

    return 0;

}

Джава

// Java реализация подхода

class GFG

{

  
// Функция для возврата счета
// необходимых триплетов

static int CountTriplets(int[] arr, int n)

{

    int ans = 0;

    for (int i = 0; i < n - 1; i++)

    {

  

        // Первый элемент

        // текущий под-массив

        int first = arr[i];

        for (int j = i + 1; j < n; j++) 

        {

  

            // XOR каждый элемент

            // текущий подмассив

            first ^= arr[j];

  

            // Если XOR становится 0, то

            // обновляем количество триплетов

            if (first == 0)

                ans += (j - i);

        }

    }

    return ans;

}

  
// Код драйвера

public static void main(String[] args)

{

    int arr[] = {2, 5, 6, 4, 2};

    int n = arr.length;

  

    System.out.println(CountTriplets(arr, n));

}

  
// Этот код предоставлен Принчи Сингхом

python3

# Python3 реализация подхода

  
# Функция для возврата счета
Количество требуемых триплетов

def CountTriplets(arr, n):

  

    ans = 0

    for i in range(n - 1):

  

        # Первый элемент

        # текущий под-массив

        first = arr[i]

        for j in range(i + 1, n):

  

            # XOR каждый элемент

            # текущий под-массив

            first ^= arr[j]

  

            # Если XOR становится 0, то

            # обновить количество триплетов

            if (first == 0):

                ans += (j - i)

  

    return ans

  
# Код драйвера

arr = [2, 5, 6, 4, 2 ]

n = len(arr)

print(CountTriplets(arr, n))

  
# Этот код предоставлен Мохитом Кумаром

C #

// C # реализация подхода

using System;

  

class GFG

{

  

    // Функция для возврата счета

    // необходимых триплетов

    static int CountTriplets(int[] arr, int n)

    {

        int ans = 0;

        for (int i = 0; i < n - 1; i++)

        {

      

            // Первый элемент

            // текущий под-массив

            int first = arr[i];

            for (int j = i + 1; j < n; j++) 

            {

      

                // XOR каждый элемент

                // текущий подмассив

                first ^= arr[j];

      

                // Если XOR становится 0, то

                // обновляем количество триплетов

                if (first == 0)

                    ans += (j - i);

            }

        }

        return ans;

    }

      

    // Код драйвера

    public static void Main()

    {

        int []arr = {2, 5, 6, 4, 2};

        int n = arr.Length;

      

        Console.WriteLine(CountTriplets(arr, n));

    }

}

  
// Этот код предоставлен AnkitRai01

Выход:

2

Сложность времени: O (n 2 )

Рекомендуемые посты:

Количество триплетов, удовлетворяющих данному уравнению

0.00 (0%) 0 votes