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

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

Дан массив 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] где ^ - побитовое исключающее ИЛИ.

Примеры:

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

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

Наивный подход: рассмотрите каждый триплет и проверьте, равен ли 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.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to return the count
// of required triplets
int CountTriplets(int* arr, int n)
{
    int ans = 0;
    for (int i = 0; i < n - 1; i++) {
  
        // First element of the
        // current sub-array
        int first = arr[i];
        for (int j = i + 1; j < n; j++) {
  
            // XOR every element of
            // the current sub-array
            first ^= arr[j];
  
            // If the XOR becomes 0 then
            // update the count of triplets
            if (first == 0)
                ans += (j - i);
        }
    }
    return ans;
}
  
// Driver code
int main()
{
    int arr[] = { 2, 5, 6, 4, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
  
    cout << CountTriplets(arr, n);
  
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
  
// Function to return the count
// of required triplets
static int CountTriplets(int[] arr, int n)
{
    int ans = 0;
    for (int i = 0; i < n - 1; i++)
    {
  
        // First element of the
        // current sub-array
        int first = arr[i];
        for (int j = i + 1; j < n; j++) 
        {
  
            // XOR every element of
            // the current sub-array
            first ^= arr[j];
  
            // If the XOR becomes 0 then
            // update the count of triplets
            if (first == 0)
                ans += (j - i);
        }
    }
    return ans;
}
  
// Driver code
public static void main(String[] args)
{
    int arr[] = {2, 5, 6, 4, 2};
    int n = arr.length;
  
    System.out.println(CountTriplets(arr, n));
}
} 
  
// This code is contributed by Princi Singh

Python3

# Python3 implementation of the approach
  
# Function to return the count
# of required triplets
def CountTriplets(arr, n):
  
    ans = 0
    for i in range(n - 1):
  
        # First element of the
        # current sub-array
        first = arr[i]
        for j in range(i + 1, n):
  
            # XOR every element of
            # the current sub-array
            first ^= arr[j]
  
            # If the XOR becomes 0 then
            # update the count of triplets
            if (first == 0):
                ans += (j - i)
  
    return ans
  
# Driver code
arr = [2, 5, 6, 4, 2 ]
n = len(arr)
print(CountTriplets(arr, n))
  
# This code is contributed by Mohit Kumar

C#

// C# implementation of the approach
using System;
  
class GFG
{
  
    // Function to return the count
    // of required triplets
    static int CountTriplets(int[] arr, int n)
    {
        int ans = 0;
        for (int i = 0; i < n - 1; i++)
        {
      
            // First element of the
            // current sub-array
            int first = arr[i];
            for (int j = i + 1; j < n; j++) 
            {
      
                // XOR every element of
                // the current sub-array
                first ^= arr[j];
      
                // If the XOR becomes 0 then
                // update the count of triplets
                if (first == 0)
                    ans += (j - i);
            }
        }
        return ans;
    }
      
    // Driver code
    public static void Main()
    {
        int []arr = {2, 5, 6, 4, 2};
        int n = arr.Length;
      
        Console.WriteLine(CountTriplets(arr, n));
    }
}
  
// This code is contributed by AnkitRai01

Output:

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

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

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

Алгоритмы Структуры данных

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

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

C++

Java

Python3

C#

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