Dada una array arr[] de N enteros tales que dos elementos adyacentes en la array difieren solo en una posición en su representación binaria. La tarea es encontrar si existe un cuádruple (arr[i], arr[j], arr[k], arr[l]) tal que arr[i] ^ arr[j] ^ arr[k] ^ arr[ l] = 0 . Aquí ^ denota la operación xor bit a bit y 1 ≤ i < j < k < l ≤ N .
Ejemplos:
Entrada: arr[] = {1, 3, 7, 3}
Salida: No
1 ^ 3 ^ 7 ^ 3 = 6
Entrada: arr[] = {1, 0, 2, 3, 7}
Salida: Sí
1 ^ 0 ^ 2 ^ 3 = 0
- Enfoque ingenuo: compruebe todos los cuádruples posibles si su xor es cero o no. Pero la complejidad temporal de tal solución sería N 4 , para todo N .
Complejidad del tiempo:
- Enfoque eficiente ( O (N 4 ), para N ≤ 130 ): Podemos decir que para una longitud de array mayor o igual a 130 podemos tener al menos 65 pares adyacentes, cada uno de los cuales denota xor de dos elementos. Aquí se da que todos los elementos adyacentes difieren en una sola posición en su forma binaria, por lo que resultaría en un solo bit establecido. Como solo tenemos 64 posiciones posibles, podemos decir que al menos dos pares tendrán el mismo xor. Así, xor de estos 4 enteros será 0 . Para N < 130 podemos usar el enfoque ingenuo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
const int MAX = 130;
// Function that returns true if the array
// contains a valid quadruplet pair
bool validQuadruple(int arr[], int n)
{
// We can always find a valid quadruplet pair
// for array size greater than MAX
if (n >= MAX)
return true;
// For smaller size arrays, perform brute force
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
for (int k = j + 1; k < n; k++)
for (int l = k + 1; l < n; l++) {
if ((arr[i] ^ arr[j] ^ arr[k] ^ arr[l]) == 0) {
return true;
}
}
return false;
}
// Driver code
int main()
{
int arr[] = { 1, 0, 2, 3, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
if (validQuadruple(arr, n))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
static int MAX = 130;
// Function that returns true if the array
// contains a valid quadruplet pair
static boolean validQuadruple(int arr[], int n)
{
// We can always find a valid quadruplet pair
// for array size greater than MAX
if (n >= MAX)
return true;
// For smaller size arrays, perform brute force
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
for (int k = j + 1; k < n; k++)
for (int l = k + 1; l < n; l++)
{
if ((arr[i] ^ arr[j] ^
arr[k] ^ arr[l]) == 0)
{
return true;
}
}
return false;
}
// Driver code
public static void main (String[] args)
throws java.lang.Exception
{
int arr[] = { 1, 0, 2, 3, 7 };
int n = arr.length;
if (validQuadruple(arr, n))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by nidhiva
Python3
# Python3 implementation of the approach
MAX = 130
# Function that returns true if the array
# contains a valid quadruplet pair
def validQuadruple(arr, n):
# We can always find a valid quadruplet pair
# for array size greater than MAX
if (n >= MAX):
return True
# For smaller size arrays,
# perform brute force
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
for l in range(k + 1, n):
if ((arr[i] ^ arr[j] ^
arr[k] ^ arr[l]) == 0):
return True
return False
# Driver code
arr = [1, 0, 2, 3, 7]
n = len(arr)
if (validQuadruple(arr, n)):
print("Yes")
else:
print("No")
# This code is contributed
# by Mohit Kumar
C#
// C# implementation of the approach
using System;
class GFG
{
static int MAX = 130;
// Function that returns true if the array
// contains a valid quadruplet pair
static Boolean validQuadruple(int []arr, int n)
{
// We can always find a valid quadruplet pair
// for array size greater than MAX
if (n >= MAX)
return true;
// For smaller size arrays, perform brute force
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
for (int k = j + 1; k < n; k++)
for (int l = k + 1; l < n; l++)
{
if ((arr[i] ^ arr[j] ^
arr[k] ^ arr[l]) == 0)
{
return true;
}
}
return false;
}
// Driver code
public static void Main (String[] args)
{
int []arr = { 1, 0, 2, 3, 7 };
int n = arr.Length;
if (validQuadruple(arr, n))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by 29AjayKumar
PHP
<?php
// PHP implementation of the approach
const MAX = 130;
// Function that returns true if the array
// contains a valid quadruplet pair
function validQuadruple($arr, $n)
{
// We can always find a valid quadruplet pair
// for array size greater than MAX
if ($n >= MAX)
return true;
// For smaller size arrays,
// perform brute force
for ($i = 0; $i < $n; $i++)
for ($j = $i + 1; $j < $n; $j++)
for ($k = $j + 1; $k < $n; $k++)
for ($l = $k + 1; $l < $n; $l++)
{
if (($arr[$i] ^ $arr[$j] ^
$arr[$k] ^ $arr[$l]) == 0)
{
return true;
}
}
return false;
}
// Driver code
$arr = array(1, 0, 2, 3, 7);
$n = count($arr);
if (validQuadruple($arr, $n))
echo ("Yes");
else
echo ("No");
// This code is contributed by Naman_Garg
?>
Javascript
<script>
// Javascript implementation
// of the approach
const MAX = 130;
// Function that returns true if the array
// contains a valid quadruplet pair
function validQuadruple(arr, n)
{
// We can always find a valid quadruplet pair
// for array size greater than MAX
if (n >= MAX)
return true;
// For smaller size arrays, perform brute force
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++)
for (let k = j + 1; k < n; k++)
for (let l = k + 1; l < n; l++) {
if ((arr[i] ^ arr[j] ^ arr[k] ^
arr[l]) == 0) {
return true;
}
}
return false;
}
// Driver code
let arr = [ 1, 0, 2, 3, 7 ];
let n = arr.length;
if (validQuadruple(arr, n))
document.write("Yes");
else
document.write("No");
</script>
Producción:
Yes
- Complejidad del tiempo:
- Espacio Auxiliar: O(1)
- Otro enfoque eficiente ( O (N 2 log N), para N ≤ 130 ):
Calcule Xor de todos los pares y haga un hash. es decir, almacene los índices i y j en una lista y córtelos en formato <xor, list>. Si se vuelve a encontrar el mismo xor para diferentes i y j, entonces tenemos un par cuádruple.
A continuación se muestra la implementación del enfoque anterior:
Java
// Java implementation of the approach
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
public class QuadrapuleXor {
static boolean check(int arr[])
{
int n = arr.length;
if(n < 4)
return false;
if(n >=130)
return true;
Map<Integer,List<Integer>> map = new HashMap<>();
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
int k = arr[i] ^ arr[j];
if(!map.containsKey(k))
map.put(k,new LinkedList<>());
List<Integer> data = map.get(k);
if(!data.contains(i) && !data.contains(j))
{
data.add(i);
data.add(j);
if(data.size()>=4)
return true;
map.put(k, data);
}
}
}
return false;
}
// Driver code
public static void main (String[] args)
throws java.lang.Exception
{
int arr[] = { 1, 0, 2, 3, 7 };
if (check(arr))
System.out.println("Yes");
else
System.out.println("No");
}
}
//This code contributed by Pramod Hosahalli
Python3
# Python3 implementation of the approach
def check(arr):
n = len(arr)
# if n is less than 4, no quadruplet
# can be possibly formed
if(n < 4):
return False
# if n >= 130, there is guaranteed
# to be a quadruplet
if(n >=130):
return True
# initializing a dictionary
map = dict()
# building the map
for i in range(n - 1):
for j in range(i + 1, n):
k = arr[i] ^ arr[j]
if k not in map:
map[k] = []
data = map[k]
if i not in data and j not in data:
data.append(i)
data.append(j)
# if a quadruplet has been found
# return true
if (len(data) >= 4):
return True
map[k] = data
return False
# Driver code
arr=[ 1, 0, 2, 3, 7 ]
if (check(arr)):
print("Yes")
else:
print("No")
# This code is contributed by phasing17
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
public class QuadrapuleXor {
// Function to check whether a quadruplet with XOR 0
// exists in the given array
static bool check(int[] arr)
{
int n = arr.Length;
if (n < 4)
return false;
if (n >= 130)
return true;
Dictionary<int, List<int> > map
= new Dictionary<int, List<int> >();
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int k = arr[i] ^ arr[j];
if (!map.ContainsKey(k))
map[k] = new List<int>();
List<int> data = map[k];
if (!data.Contains(i)
&& !data.Contains(j)) {
data.Add(i);
data.Add(j);
if (data.Count >= 4)
return true;
map[k] = data;
}
}
}
return false;
}
// Driver code
public static void Main(string[] args)
{
int[] arr = { 1, 0, 2, 3, 7 };
// Function Call
if (check(arr))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by phasing17
Javascript
<script>
// Javascript implementation of the approach
function check(arr)
{
let n = arr.length;
if(n < 4)
return false;
if(n >=130)
return true;
let map = new Map();
for(let i=0;i<n-1;i++)
{
for(let j=i+1;j<n;j++)
{
let k = arr[i] ^ arr[j];
if(!map.has(k))
map.set(k,[]);
let data = map.get(k);
if(!data.includes(i) && !data.includes(j))
{
data.push(i);
data.push(j);
if(data.length>=4)
return true;
map.set(k, data);
}
}
}
return false;
}
// Driver code
let arr=[ 1, 0, 2, 3, 7 ];
if (check(arr))
document.write("Yes<br>");
else
document.write("No<br>");
// This code is contributed by rag2127
</script>
Producción:
Yes
- Complejidad del tiempo:
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por GreenCoder y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA