Dadas tres arrays binarias, cada una de tamaño n , la tarea es encontrar el cambio mínimo de bits en la primera y segunda array de modo que el XOR del i-ésimo bit de índice de la primera y la segunda array sea igual al i-ésimo bit de índice de la tercera. formación. Dada una restricción que solo podemos voltear como máximo p bits de la array 1 y como máximo q bits de la array 2. Si no es posible, genera -1.
No se permite el reordenamiento de bits.
Ejemplos:
Input : p = 2, q = 2
arr1[] = {0, 0, 1}
arr2[] = {0, 1, 0}
arr3[] = {0, 1, 0}
Output : 1
arr1[0] ^ arr2[0] = 0 ^ 0 = 0, which is equal
to arr3[0], so no flip required.
arr1[1] ^ arr2[1] = 0 ^ 1 = 1, which is equal
to arr3[1], so no flip required.
arr1[2] ^ arr2[2] = 1 ^ 0 = 1, which is not
equal to arr3[0], so one flip required.
Also p = 2 and q = 2, so flip arr1[2].
Input : p = 2, q = 4
arr1 = { 1, 0, 1, 1, 1, 1, 1 }
arr2 = { 0, 1, 1, 1, 1, 0, 0 }
arr3 = { 1, 1, 1, 1, 0, 0, 1 }
Output : 3
When the XOR of i'th bit of array1 and arry2 is
equal to i'th bit of array3, no flip is required.
Now let's observe when XOR is not equal.
There can be following cases:
Case 1: When arr3[i] = 0,
then either arr1[i] = 1, arr2[i] = 0 or
arr1[i] = 0, arr2[i] = 1.
Case 2: When arr3[i] = 1,
then either arr1[i] = 1, arr2[i] = 1 or
arr1[i] = 0, arr2[i] = 0.
At least one flip is required in each case.
Para el caso 1, XOR debe ser 0, que se puede obtener con 0 ^ 0 o 1 ^ 1 y para el caso 2, 1 se puede obtener con 1 ^ 0 o 0 ^ 1.
Por lo tanto, observe que podemos invertir arr1[i] o arr2[i] dependiendo del valor de p y q.
Si p = 0, flip arr2 debe ser flip y si q también es 0, genera -1. Y de manera similar, si p = 0, flip arr1 debe ser flip y si p también es 0, salida -1
Entonces, podemos decir que el número de flips necesarios para hacer XOR de arr1 y arr2 igual a arr3 debe ser menor o igual a p + q.
Implementación:
C++
// C++ program to find minimum flip required to make
// XOR of two arrays equal to another array with
// constraints on number of flip on each array.
#include <bits/stdc++.h>
using namespace std;
// Return minimum number of flip required
int minflip(int arr1[], int arr2[], int arr3[],
int p, int q, int n)
{
int flip = 0;
// Counting number of mismatch, XOR of arr1[] and
// arr2[] is not equal to arr3[].
for (int i = 0; i < n; i++)
if (arr1[i] ^ arr2[i] != arr3[i])
flip++;
// if flip is less then allowed constraint return
// it. else return -1.
return (flip <= p + q) ? flip : -1;
}
// Driven Program
int main()
{
int arr1[] = { 1, 0, 1, 1, 1, 1, 1 };
int arr2[] = { 0, 1, 1, 1, 1, 0, 0 };
int arr3[] = { 1, 1, 1, 1, 0, 0, 1 };
int n = sizeof(arr1) / sizeof(arr1[0]);
int p = 2, q = 4;
cout << minflip(arr1, arr2, arr3, p, q, n);
return 0;
}
Java
// Java program to find minimum flip required to make
// XOR of two arrays equal to another array with
// constraints on number of flip on each array.
import java.io.*;
class GFG {
// Return minimum number of flip required
static int minflip(int[] arr1, int[] arr2, int[] arr3,
int p, int q, int n)
{
int flip = 0;
// Counting number of mismatch, XOR of arr1[] and
// arr2[] is not equal to arr3[].
for (int i = 0; i < n; i++)
if (arr1[i] > 0 ^ arr2[i] > 0 != arr3[i] > 0)
flip++;
// if flip is less then allowed constraint return
// it. else return -1.
return (flip <= p + q) ? flip : -1;
}
// Driver program
static public void main(String[] args)
{
int[] arr1 = {1, 0, 1, 1, 1, 1, 1};
int[] arr2 = {0, 1, 1, 1, 1, 0, 0};
int[] arr3 = {1, 1, 1, 1, 0, 0, 1};
int n = arr1.length;
int p = 2, q = 4;
System.out.println(minflip(arr1, arr2, arr3, p, q, n));
}
}
// This code is contributed by vt_m.
Python3
# Python 3 program to find # minimum flip required to # make XOR of two arrays # equal to another array # with constraints on number # of flip on each array. # Return minimum number # of flip required def minflip(arr1, arr2, arr3, p, q, n): flip = 0 # Counting number of # mismatch, XOR of # arr1[] and arr2[] # is not equal to arr3[]. for i in range(0 , n): if (arr1[i] ^ arr2[i] != arr3[i]): flip += 1 # if flip is less then # allowed constraint return # it. else return -1. return flip if (flip <= p + q) else -1 # Driver Code arr1 = [1, 0, 1, 1, 1, 1, 1] arr2 = [0, 1, 1, 1, 1, 0, 0] arr3 = [1, 1, 1, 1, 0, 0, 1] n = len(arr1) p = 2 q = 4 print(minflip(arr1, arr2, arr3, p, q, n)) # This code is contributed # by Smitha
C#
// C# program to find minimum flip required to make
// XOR of two arrays equal to another array with
// constraints on number of flip on each array.
using System;
class GFG {
// Return minimum number of flip required
static int minflip(int[] arr1, int[] arr2, int[] arr3,
int p, int q, int n)
{
int flip = 0;
// Counting number of mismatch, XOR of arr1[] and
// arr2[] is not equal to arr3[].
for (int i = 0; i < n; i++)
if (arr1[i] > 0 ^ arr2[i] > 0 != arr3[i] > 0)
flip++;
// if flip is less then allowed constraint return
// it. else return -1.
return (flip <= p + q) ? flip : -1;
}
// Driver program
static public void Main()
{
int[] arr1 = { 1, 0, 1, 1, 1, 1, 1 };
int[] arr2 = { 0, 1, 1, 1, 1, 0, 0 };
int[] arr3 = { 1, 1, 1, 1, 0, 0, 1 };
int n = arr1.Length;
int p = 2, q = 4;
Console.WriteLine(minflip(arr1, arr2, arr3, p, q, n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find minimum
// flip required to make XOR
// of two arrays equal to another
// array with constraints on number
// of flip on each array.
// Return minimum number
// of flip required
function minflip($arr1, $arr2, $arr3,
$p, $q, $n)
{
$flip = 0;
// Counting number of mismatch,
// XOR of arr1[] and arr2[]
// is not equal to arr3[].
for ($i = 0; $i < $n; $i++)
if ($arr1[$i] ^ $arr2[$i] != $arr3[$i])
$flip++;
// if flip is less then
// allowed constraint return
// it. else return -1.
return ($flip <= $p + $q) ? $flip : -1;
}
// Driver code
$arr1 = array(1, 0, 1, 1, 1, 1, 1);
$arr2 = array(0, 1, 1, 1, 1, 0, 0);
$arr3 = array(1, 1, 1, 1, 0, 0, 1);
$n = count($arr1);
$p = 2; $q = 4;
echo minflip($arr1, $arr2, $arr3, $p, $q, $n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find
// minimum flip required to make
// XOR of two arrays equal to
// another array with
// constraints on number of
// flip on each array.
// Return minimum number
// of flip required
function minflip(arr1, arr2, arr3, p, q, n)
{
let flip = 0;
// Counting number of mismatch,
// XOR of arr1[] and
// arr2[] is not equal to arr3[].
for (let i = 0; i < n; i++)
if (arr1[i] ^ arr2[i] != arr3[i])
flip++;
// if flip is less then
// allowed constraint return
// it. else return -1.
return (flip <= p + q) ? flip : -1;
}
// Driven Program
let arr1 = [ 1, 0, 1, 1, 1, 1, 1 ];
let arr2 = [ 0, 1, 1, 1, 1, 0, 0 ];
let arr3 = [ 1, 1, 1, 1, 0, 0, 1 ];
let n = arr1.length;
let p = 2, q = 4;
document.write(minflip(arr1, arr2, arr3, p, q, n));
</script>
3
Complejidad temporal: O(n).
Este artículo es una contribución de Anuj Chauhan . 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