Cuente todos los tripletes de un Array dado cuyo bit a bit XOR es igual a K

Dada una array arr[] que contiene N enteros positivos y un entero K . La tarea es contar todos los tripletes cuyo XOR sea igual a K . es decir, arr[ i ] ^ arr[ j ] ^ arr[ k ] = X  donde 0 ≤ i < j < k < N (indexación basada en 0)

Ejemplos:

Entrada: arr[] = { 2, 1, 3, 7, 5, 4}, K = 5
Salida: 2
Explicación: En la array anterior hay dos tripletas cuyo xor es igual a K
{ 2, 3, 4}, ( 2 ^ 3 ^ 4 = 5) 
{1, 3, 7}, ( 1 ^ 3 ^ 7 = 5 )
Entonces, la salida es 2. 

Entrada: arr[] = { 4, 1, 5, 7}, X=0
Salida: 1
Explicación: En la array anterior solo hay un triplete cuyo xor es igual a K
{ 4, 1, 5} (4 ^ 1 ^ 5=0)

Enfoque ingenuo: un enfoque simple es verificar cada triplete, si es bit a bit xor es igual a K , entonces aumente el conteo en 1.
Y finalmente, devuelva el conteo.

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

// C++ code to implement the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Count of all valid triplets
int count_triplets(int arr[], int N, int K)
{
    int cnt = 0;
 
    // Fixed first element as arr[i]
    for (int i = 0; i < N; i++) {
 
        // Fixed second element as arr[j]
        for (int j = i + 1; j < N; j++) {
 
            // Now look for third element
            for (int k = j + 1; k < N; k++) {
                int triplet_xor = arr[i] ^ arr[j] ^ arr[k];
 
                // If xor is equal to K
                // increase cnt by 1.
                if (triplet_xor == K) {
                    cnt++;
                }
            }
        }
    }
    return cnt;
}
 
// Driver code
int main()
{
    int N = 6;
    int arr[] = { 2, 1, 3, 7, 5, 4 };
    int K = 5;
 
    // Function call
    cout << count_triplets(arr, N, K);
    return 0;
}

// C code to implement the approach
 
#include <stdio.h>
 
// Function to count of all valid triplets
int count_triplets(int arr[], int N, int K)
{
    int cnt = 0;
 
    // Fixed first element as arr[i]
    for (int i = 0; i < N; i++) {
 
        // Fixed second element as arr[j]
        for (int j = i + 1; j < N; j++) {
 
            // Now look for third element
            for (int k = j + 1; k < N; k++) {
                int triplet_xor
                    = arr[i] ^ arr[j] ^ arr[k];
 
                // If xor is equal to X
                // increase cnt by 1.
                if (triplet_xor == K) {
                    cnt++;
                }
            }
        }
    }
    return cnt;
}
 
// Driver code
int main()
{
    int N = 6;
    int arr[] = { 2, 1, 3, 7, 5, 4 };
    int K = 5;
 
    // Function call
    printf("%d", count_triplets(arr, N, K));
    return 0;
}

// Java code to implement the approach
 
import java.util.*;
 
class FindTriplet {
 
    // Function to count all triplets
    int count_triplets(int arr[], int N, int K)
    {
        int cnt = 0;
 
        // Fix the first element as arr[i]
        for (int i = 0; i < N; i++) {
 
            // Fix the second element as arr[j]
            for (int j = i + 1; j < N; j++) {
 
                // Now look for the third number
                for (int k = j + 1; k < N;
                     k++) {
                    int triplet_xor
                        = arr[i] ^ arr[j]
                          ^ arr[k];
 
                    // If xor is equal to X
                    // increase cnt by 1.
                    if (triplet_xor == K) {
                        cnt++;
                    }
                }
            }
        }
 
        return cnt;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        FindTriplet triplet = new FindTriplet();
        int N = 6;
        int arr[] = { 2, 1, 3, 7, 5, 4 };
        int K = 5;
 
        // Function call
        System.out.print(triplet.count_triplets(arr, N, K));
    }
}

# Python3 code for the above approach
 
# Count of all valid triplets
def count_triplets(arr, N, K):
 
    cnt = 0
 
    # Fixed first element as arr[i]
    for i in range(N):
       
        # Fixed second element as arr[j]
        for j in range(i + 1, N):
           
            # Now look for third element
            for k in range(j + 1, N):
                triplet_xor = arr[i] ^ arr[j] ^ arr[k]
                 
                # If xor is equal to K
                # increase cnt by 1.
                if triplet_xor == K:
                    cnt += 1
 
    return cnt
 
# Driver code
N = 6
arr = [2, 1, 3, 7, 5, 4]
K = 5
 
# function call
print(count_triplets(arr, N, K))
 
# This code was contributed by phasing17

// C# code to implement the approach
using System;
 
class GFG
{
 
  // Function to count all triplets
  static int count_triplets(int[] arr, int N, int K)
  {
    int cnt = 0;
 
    // Fix the first element as arr[i]
    for (int i = 0; i < N; i++) {
 
      // Fix the second element as arr[j]
      for (int j = i + 1; j < N; j++) {
 
        // Now look for the third number
        for (int k = j + 1; k < N; k++) {
          int triplet_xor
            = arr[i] ^ arr[j] ^ arr[k];
 
          // If xor is equal to X
          // increase cnt by 1.
          if (triplet_xor == K) {
            cnt++;
          }
        }
      }
    }
 
    return cnt;
  }
 
  // Driver code
  public static int Main()
  {
    int N = 6;
    int[] arr = new int[] { 2, 1, 3, 7, 5, 4 };
    int K = 5;
 
    // Function call
    Console.Write(count_triplets(arr, N, K));
    return 0;
  }
}
 
// This code is contributed by Taranpreet

<script>
    // JavaScript code to implement the above approach
 
    // Count of all valid triplets
    const count_triplets = (arr, N, K) => {
        let cnt = 0;
 
        // Fixed first element as arr[i]
        for (let i = 0; i < N; i++) {
 
            // Fixed second element as arr[j]
            for (let j = i + 1; j < N; j++) {
 
                // Now look for third element
                for (let k = j + 1; k < N; k++) {
                    let triplet_xor = arr[i] ^ arr[j] ^ arr[k];
 
                    // If xor is equal to K
                    // increase cnt by 1.
                    if (triplet_xor == K) {
                        cnt++;
                    }
                }
            }
        }
        return cnt;
    }
 
    // Driver code
    let N = 6;
    let arr = [2, 1, 3, 7, 5, 4];
    let K = 5;
 
    // Function call
    document.write(count_triplets(arr, N, K));
 
// This code is contributed by rakeshsahni
 
</script>

2

Complejidad temporal: O(N ³⁾
Espacio auxiliar: O(1)

Enfoque eficiente: el problema se puede resolver de manera eficiente mediante el uso de propiedades de clasificación , búsqueda binaria y xor basadas en la siguiente idea:

Ordene la array y luego ejecute dos bucles anidados para seleccionar dos elementos del posible triplete. Use la búsqueda binaria para encontrar si el tercer elemento está presente o no con la ayuda de la propiedad Xor (si a ^ x = K entonces a ^ K = x). Si se encuentra, entonces existe un triplete posible.

Siga los pasos a continuación para implementar la idea:

• Ordena la array dada en orden no decreciente.
• Haz un bucle for que apunte hacia el primer número de tripletes.
  • Haz un bucle for anidado que apuntará hacia el segundo número de un triplete
    • El tercer número será: third_ele = X ^ arr[ i ] ^ arr[ j ] , porque si a^b^c = d entonces c = d^a^b (propiedad xor). 
    • Haz una búsqueda binaria en [ j+1, N-1 ]. Si el tercer elemento está presente en este rango, aumente la cuenta en 1.
• Finalmente regresa la cuenta .

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count all valid triplets
int count_triplets(int arr[], int N, int K)
{
    // Sort array to perform lower_bound
    sort(arr, arr + N);
    int cnt = 0;
 
    // Fixed arr[i] as a first element
    for (int i = 0; i < N; i++) {
 
        // Fixed arr[j] as a second element
        for (int j = i + 1; j < N; j++) {
            int third_ele = K ^ arr[i] ^ arr[j];
 
            // Find third element
            auto it = lower_bound(arr + j + 1,
                                  arr + N, third_ele)
                      - arr;
            // If third element is present
            // then increase cnt by 1
            if (it != N && arr[it] == third_ele)
                cnt++;
        }
    }
 
    return cnt;
}
 
// Driver code
int main()
{
    int N = 6;
    int arr[] = { 2, 1, 3, 7, 5, 4 };
    int K = 5;
 
    // Function call
    cout << count_triplets(arr, N, K);
    return 0;
}

// Java code to implement the approach
import java.io.*;
import java.util.*;
 
class GFG
{
 
  // Function to find lower bound using binary search
  public static int lower_bound(int a[], int x, int l)
  {
 
    // x is the target value or key
    int r = a.length;
    while (l + 1 < r) {
      int m = (l + r) >>> 1;
      if (a[m] >= x)
        r = m;
      else
        l = m;
    }
    return r;
  }
  // Function to count all valid triplets
  public static int count_triplets(int arr[], int N,
                                   int K)
  {
    // Sort array to perform lower_bound
    Arrays.sort(arr);
    int cnt = 0;
 
    // Fixed arr[i] as a first element
    for (int i = 0; i < N; i++) {
 
      // Fixed arr[j] as a second element
      for (int j = i + 1; j < N; j++) {
        int third_ele = K ^ arr[i] ^ arr[j];
 
        // Find third element
        int it = lower_bound(arr, third_ele, j);
 
        // If third element is present
        // then increase cnt by 1
        if (it != N && arr[it] == third_ele)
          cnt++;
      }
    }
 
    return cnt;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int N = 6;
    int arr[] = { 2, 1, 3, 7, 5, 4 };
    int K = 5;
 
    // Function call
    System.out.print(count_triplets(arr, N, K));
  }
}
 
// This code is contributed by Rohit Pradhan

# Python3 code for the above approach
 
# Function to find lower bound using binary search
def lower_bound(a, x, l):
   
    # x is the target value or key
    r = len(a)
    while (l + 1 < r):
        m = (l + r) >> 1
        if a[m] >= x:
            r = m
        else:
            l = m
    return r
 
# Function to count all valid triplets
def count_triplets(arr, N, K):
   
    # sort array to perform lower_bound
    arr.sort()
    cnt = 0
     
    # Fixed arr[i] as a first element
    for i in range(N):
       
        # Fixed arr[j] as a second element
        for j in range(i + 1, N):
            third_ele = K ^ arr[i] ^ arr[j]
             
            # Find third element
            it = lower_bound(arr, third_ele, j)
             
            # If third element is present
            # then increase cnt by 1
            if it != N and arr[it] == third_ele:
                cnt += 1
    return cnt
 
# Driver Code
N = 6
arr = [ 2, 1, 3, 7, 5, 4 ]
K = 5
 
# Function call
print(count_triplets(arr, N, K))
 
# this code is contributed by phasing17

// C# program for above approach
using System;
class GFG
{
 
  // Function to find lower bound using binary search
  public static int lower_bound(int[] a, int x, int l)
  {
 
    // x is the target value or key
    int r = a.Length;
    while (l + 1 < r) {
      int m = (l + r) >> 1;
      if (a[m] >= x)
        r = m;
      else
        l = m;
    }
    return r;
  }
  // Function to count all valid triplets
  public static int count_triplets(int[] arr, int N,
                                   int K)
  {
    // Sort array to perform lower_bound
    Array.Sort(arr);
    int cnt = 0;
 
    // Fixed arr[i] as a first element
    for (int i = 0; i < N; i++) {
 
      // Fixed arr[j] as a second element
      for (int j = i + 1; j < N; j++) {
        int third_ele = K ^ arr[i] ^ arr[j];
 
        // Find third element
        int it = lower_bound(arr, third_ele, j);
 
        // If third element is present
        // then increase cnt by 1
        if (it != N && arr[it] == third_ele)
          cnt++;
      }
    }
 
    return cnt;
  }
 
// Driver Code
public static void Main()
{
    int N = 6;
    int[] arr = { 2, 1, 3, 7, 5, 4 };
    int K = 5;
 
    // Function call
    Console.Write(count_triplets(arr, N, K));
}
}
 
// This code is contributed by code_hunt.

<script>
    // JavaScript code for the above approach
 
  // Function to find lower bound using binary search
  function lower_bound(a, x, l)
  {
 
    // x is the target value or key
    let r = a.length;
    while (l + 1 < r) {
      let m = (l + r) >>> 1;
      if (a[m] >= x)
        r = m;
      else
        l = m;
    }
    return r;
  }
  // Function to count all valid triplets
  function count_triplets(arr, N, K)
  {
    // Sort array to perform lower_bound
    arr.sort();
    let cnt = 0;
 
    // Fixed arr[i] as a first element
    for (let i = 0; i < N; i++) {
 
      // Fixed arr[j] as a second element
      for (let j = i + 1; j < N; j++) {
        let third_ele = K ^ arr[i] ^ arr[j];
 
        // Find third element
        let it = lower_bound(arr, third_ele, j);
 
        // If third element is present
        // then increase cnt by 1
        if (it != N && arr[it] == third_ele)
          cnt++;
      }
    }
 
    return cnt;
  }
 
    // Driver code
    let N = 6;
    let arr = [ 2, 1, 3, 7, 5, 4 ];
    let K = 5;
 
    // Function call
    document.write(count_triplets(arr, N, K));
 
// This code is contributed by sanjoy_62.
</script>

2

Complejidad de Tiempo: O(N ² * logN)
Espacio Auxiliar: O(1)