Dadas cuatro arrays y un entero x, encuentre el número de cuádruples que satisfacen a^b^c^d = x, donde a pertenece a Arr 1 , b pertenece a Arr 2 , c pertenece a Arr 3 , d pertenece a Arr 4 .
Ejemplos:
Input : x = 0;
a[] = { 1 , 10 };
b[] = { 1 , 10 };
c[] = { 1 , 10 };
d[] = { 1 , 10 };
Output : 4
Explanation: There are total 8 Quadruples
with XOR value equals to 0.
{1, 1, 1, 1}, {10, 10, 10, 10}, {1, 1, 10, 10},
{10, 10, 1, 1}, {10, 1, 10, 1}, {1, 10, 1, 10},
{1, 10, 10, 1}, {10, 1, 1, 10}
Input : x = 3
a[] = {0, 1}
b[] = {2, 0}
c[] = {0, 1}
d[] = {0, 1}
Output : 4
Explanation: There are total 4 Quadruples
with XOR value equals to 3.
{0, 2, 0, 1}, {1, 2, 0, 0}, {0, 2, 1, 0},
{1, 2, 1, 1}
Método 1 (enfoque ingenuo): se puede hacer usando 4 bucles, cubriendo cada cuádruple y verificando si es igual ax o no.
Implementación:
C++
// C++ program to find number of Quadruples from four
// arrays such that their XOR equals to 'x'
#include<bits/stdc++.h>
using namespace std;
// Function to return the number of Quadruples with XOR
// equals to x such that every element of Quadruple is
// from different array.
int findQuadruples(int a[], int b[], int c[], int d[],
int x, int n)
{
int count = 0;
for (int i = 0 ; i < n ; i++)
for (int j = 0 ; j < n ; j++)
for (int k = 0 ; k < n ; k++)
for (int l = 0 ; l < n ; l++)
// Check whether XOR is equal to x
if ((a[i] ^ b[j] ^ c[k] ^ d[l]) == x)
count++;
return count;
}
// Driver Program
int main()
{
int x = 3;
int a[] = {0, 1};
int b[] = {2, 0};
int c[] = {0, 1};
int d[] = {0, 1};
int n = sizeof(a)/sizeof(a[0]);
cout << findQuadruples(a, b, c, d, x, n) << endl;
return 0;
}
Java
// Java program to find number of Quadruples from four
// arrays such that their XOR equals to 'x'
class GFG {
// Function to return the number of Quadruples with XOR
// equals to x such that every element of Quadruple is
// from different array.
static int findQuadruples(int a[], int b[], int c[],
int d[], int x, int n)
{
int count = 0;
for (int i = 0 ; i < n ; i++)
for (int j = 0 ; j < n ; j++)
for (int k = 0 ; k < n ; k++)
for (int l = 0 ; l < n ; l++)
// Check whether XOR is equal to x
if ((a[i] ^ b[j] ^ c[k] ^ d[l]) == x)
count++;
return count;
}
// Driver method
public static void main(String[] args)
{
int x = 3;
int a[] = {0, 1};
int b[] = {2, 0};
int c[] = {0, 1};
int d[] = {0, 1};
int n = a.length;
System.out.println(findQuadruples(a, b, c, d, x, n));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to find number of # Quadruples from four arrays such # that their XOR equals to 'x' # Function to return the number of # Quadruples with XOR equals to x # such that every element of Quadruple # is from different array. def findQuadruples(a, b, c, d, x, n): count = 0 for i in range(n): for j in range(n): for k in range(n): for l in range(n): # Check whether XOR is equal to x if ((a[i] ^ b[j] ^ c[k] ^ d[l]) == x): count += 1 return count # Driver Code x = 3 a = [0, 1] b = [2, 0] c = [0, 1] d = [0, 1] n = len(a) print(findQuadruples(a, b, c, d, x, n)) # This code is contributed by Anant Agarwal.
C#
// C# program to find number of
// Quadruples from four arrays such
// that their XOR equals to 'x'
using System;
class GFG {
// Function to return the number of
// Quadruples with XOR equals to x such that
// every element of Quadruple is from different array.
static int findQuadruples(int []a, int []b, int []c,
int []d, int x, int n)
{
int count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
for (int l = 0; l < n; l++)
// Check whether XOR is equal to x
if ((a[i] ^ b[j] ^ c[k] ^ d[l]) == x)
count++;
return count;
}
// Driver method
public static void Main()
{
int x = 3;
int []a = {0, 1};
int []b = {2, 0};
int []c = {0, 1};
int []d = {0, 1};
int n = a.Length;
// Function calling
Console.Write(findQuadruples(a, b, c, d, x, n));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to find number
// of Quadruples from four
// arrays such that their
// XOR equals to 'x'
// Function to return the number
// of Quadruples with XOR equals
// to x such that every element
// of Quadruple is from different
// array.
function findQuadruples($a, $b, $c,
$d, $x, $n)
{
$count = 0;
for ($i = 0 ; $i < $n ; $i++)
for ($j = 0 ; $j < $n ; $j++)
for ($k = 0 ; $k < $n ; $k++)
for ($l = 0 ; $l < $n ; $l++)
// Check whether XOR
// is equal to x
if (($a[$i] ^ $b[$j] ^
$c[$k] ^ $d[$l]) == $x)
$count++;
return $count;
}
// Driver Code
$x = 3;
$a = array(0, 1);
$b = array(2, 0);
$c = array(0, 1);
$d = array(0, 1);
$n = count($a);
echo findQuadruples($a, $b, $c, $d, $x, $n) ;
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find number of Quadruples from four
// arrays such that their XOR equals to 'x'
// Function to return the number of Quadruples with XOR
// equals to x such that every element of Quadruple is
// from different array.
function findQuadruples(a, b, c, d, x, n)
{
let count = 0;
for (let i = 0 ; i < n ; i++)
for (let j = 0 ; j < n ; j++)
for (let k = 0 ; k < n ; k++)
for (let l = 0 ; l < n ; l++)
// Check whether XOR is equal to x
if ((a[i] ^ b[j] ^ c[k] ^ d[l]) == x)
count++;
return count;
}
let x = 3;
let a = [0, 1];
let b = [2, 0];
let c = [0, 1];
let d = [0, 1];
let n = a.length;
document.write(findQuadruples(a, b, c, d, x, n));
</script>
Producción
4
Tiempo Complejidad: O(n 4 )
Espacio Auxiliar: O(1)
Método 2 (enfoque eficiente):
The idea is to use meet in the middle algorithm. For this, observe the pattern below: a ^ b ^ c ^ d = x XOR c and d both sides a ^ b ^ c ^ d ^ c ^ d = x ^ c ^ d Since, c ^ c = 0 and d ^ d = 0 a ^ b ^ 0 ^ 0 = x ^ c ^ d That is, a ^ b = x ^ c ^ d
Ahora, solo tenemos que calcular a ^ b y x ^ c ^ d, que se pueden calcular en O(n 2 ) cada uno y luego encontrar los elementos mediante la búsqueda binaria.
Implementación:
C++
// C++ program to find number of Quadruples from four
// arrays such that their XOR equals to 'x'
#include<bits/stdc++.h>
using namespace std;
// Function to return the number of Quadruples with XOR
// equals to x such that every element of Quadruple is
// from different array.
int findQuadruples(int a[], int b[], int c[], int d[],
int x, int n)
{
int count = 0;
vector<int> v1, v2;
// Loop to get two different subsets
for (int i = 0 ; i < n ; i++)
{
for (int j = 0 ; j < n ; j++)
{
// v1 for first and second array
v1.push_back(a[i]^b[j]);
// v2 for third and forth array.
// x is a constant, so no need for
// a separate loop
v2.push_back(x ^ c[i] ^ d[j]);
}
}
// Sorting the first set (Containing XOR
// of a[] and b[]
sort(v1.begin(), v1.end());
// Finding the lower and upper bound of an
// element to find its number
for (int i = 0 ; i < v2.size() ; i++)
{
// Count number of occurrences of v2[i] in sorted
// v1[] and add the count to result.
auto low = lower_bound(v1.begin(), v1.end(), v2[i]);
auto high = upper_bound(v1.begin(), v1.end(), v2[i]);
count += high - low;
}
return count;
}
// Driver Program
int main()
{
int x = 3;
int a[] = {0, 1};
int b[] = {2, 0};
int c[] = {0, 1};
int d[] = {0, 1};
int n = sizeof(a)/sizeof(a[0]);
cout << findQuadruples(a, b, c, d, x, n) << endl;
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
class GFG
{
// Function to return the number of Quadruples with XOR
// equals to x such that every element of Quadruple is
// from different array.
public static int findQuadruples(int a[], int b[],
int c[], int d[],
int x, int n)
{
int count = 0;
ArrayList<Integer> v1 = new ArrayList<>();
ArrayList<Integer> v2 = new ArrayList<>();
// Loop to get two different subsets
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
// v1 for first and second array
v1.add(a[i] ^ b[j]);
// v2 for third and forth array.
// x is a constant, so no need for
// a separate loop
v2.add(x ^ c[i] ^ d[j]);
}
}
Collections.sort(v1);
// Finding the lower and upper bound of an
// element to find its number
for (int i = 0; i < v2.size(); i++)
{
// Count number of occurrences of v2[i] in
// sorted v1[] and add the count to result.
int low
= Collections.binarySearch(v1, v2.get(i));
int j = low;
for (j = low; j >= 0; j--)
{
if (v1.get(j) != v2.get(i))
{
j++;
break;
}
}
low = j;
int high = Collections.binarySearch(v1, v2.get(i));
j = high;
for (j = high; j < v1.size(); j++)
{
if (v1.get(j) != v2.get(i)) {
break;
}
}
high = j;
count += high - low;
}
return count;
}
// Driver code
public static void main(String[] args)
{
int x = 3;
int a[] = { 0, 1 };
int b[] = { 2, 0 };
int c[] = { 0, 1 };
int d[] = { 0, 1 };
int n = 2;
System.out.println(
findQuadruples(a, b, c, d, x, n));
}
}
// This code is contributed by aditya7409
Python3
# Python3 program to find number of Quadruples # from four arrays such that their XOR equals # to 'x' from bisect import bisect_left, bisect_right # Function to return the number of Quadruples # with XOR equals to x such that every element # of Quadruple is from different array. def findQuadruples(a, b, c, d, x, n): count = 0 v1, v2 = [], [] # Loop to get two different subsets for i in range(n): for j in range(n): # v1 for first and second array v1.append(a[i] ^ b[j]) # v2 for third and forth array. # x is a constant, so no need for # a separate loop v2.append(x ^ c[i] ^ d[j]) # Sorting the first set (Containing XOR # of aand b v1 = sorted(v1) # Finding the lower and upper bound of an # element to find its number for i in range(len(v2)): # Count number of occurrences of v2[i] # in sorted v1and add the count to result. low = bisect_left(v1, v2[i]) high = bisect_right(v1, v2[i]) count += high - low return count # Driver code if __name__ == '__main__': x = 3 a = [ 0, 1 ] b = [ 2, 0 ] c = [ 0, 1 ] d = [ 0, 1 ] n = len(a) print(findQuadruples(a, b, c, d, x, n)) # This code is contributed by mohit kumar 29
C#
// C# program to find number of Quadruples from four
// arrays such that their XOR equals to 'x'
using System;
using System.Collections.Generic;
class GFG
{
// Function to return the number of Quadruples with XOR
// equals to x such that every element of Quadruple is
// from different array.
static int findQuadruples(int[] a, int[] b,
int[] c, int[] d,
int x, int n)
{
int count = 0;
List<int> v1 = new List<int>();
List<int> v2 = new List<int>();
// Loop to get two different subsets
for (int i = 0 ; i < n ; i++)
{
for (int j = 0 ; j < n ; j++)
{
// v1 for first and second array
v1.Add(a[i]^b[j]);
// v2 for third and forth array.
// x is a constant, so no need for
// a separate loop
v2.Add(x ^ c[i] ^ d[j]);
}
}
// Sorting the first set (Containing XOR
// of a[] and b[]
v1.Sort();
// Finding the lower and upper bound of an
// element to find its number
for (int i = 0 ; i < v2.Count; i++)
{
// Count number of occurrences of v2[i] in
// sorted v1[] and add the count to result.
int low = v1.BinarySearch(v2[i]);
int j = low;
for (j = low; j >= 0; j--)
{
if (v1[j] != v2[i])
{
j++;
break;
}
}
low = j;
int high = v1.BinarySearch(v2[i]);
j = high;
for (j = high; j < v1.Count; j++)
{
if (v1[j] != v2[i])
{
break;
}
}
high = j;
count += high - low;
}
return count;
}
// Driver code
static void Main()
{
int x = 3;
int[] a = {0, 1};
int[] b = {2, 0};
int[] c = {0, 1};
int[] d = {0, 1};
int n = a.Length;
Console.WriteLine(findQuadruples(a, b, c, d, x, n));
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// JavaScript program to find number of Quadruples from four
// arrays such that their XOR equals to 'x'
// Function to return the number of Quadruples with XOR
// equals to x such that every element of Quadruple is
// from different array.
function findQuadruples(a, b, c, d, x, n)
{
let count = 0;
let v1 = [];
let v2 = [];
// Loop to get two different subsets
for (let i = 0; i < n; i++)
{
for (let j = 0; j < n; j++)
{
// v1 for first and second array
v1.push(a[i] ^ b[j]);
// v2 for third and forth array.
// x is a constant, so no need for
// a separate loop
v2.push(x ^ c[i] ^ d[j]);
}
}
v1.sort();
// Finding the lower and upper bound of an
// element to find its number
for (let i = 0; i < v2.length; i++)
{
// Count number of occurrences of v2[i] in
// sorted v1[] and add the count to result.
let low = 0;
for(let z = 0; z < v1.length; z++)
{
if(v1[z] == v2[i])
{
low = z;
break;
}
}
let j = low;
for (j = low; j >= 0; j--)
{
if (v1[j] != v2[i])
{
j++;
break;
}
}
low = j;
let high = 0;
for(let z = 0; z < v1.length; z++)
{
if(v1[z] == v2[i])
{
high = z;
break;
}
}
j = high;
for (j = high; j < v1.length; j++)
{
if (v1[j] != v2[i]) {
break;
}
}
high = j;
count += high - low;
}
return count;
}
let x = 3;
let a = [ 0, 1 ];
let b = [ 2, 0 ];
let c = [ 0, 1 ];
let d = [ 0, 1 ];
let n = 2;
document.write(
findQuadruples(a, b, c, d, x, n));
</script>
Producción
4
Complejidad de Tiempo: O(n 2 log(n))
Espacio Auxiliar: O(n 2 )
Este artículo es una contribución de Shubham Gupta . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu 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