Dadas tres strings binarias S1 , S2 y S3 , cada una de longitud N , la tarea es encontrar el máximo XOR bit a bit posible que se puede obtener reorganizando los caracteres de las strings dadas.
Ejemplos:
Entrada: S1 = “1001”, S2 = “0010”, S3 = “1110”
Salida: 15
Explicación:
Reorganice los dígitos de S1 como “1010”, S2 como “1000” y S3 como “1101”.
El XOR de estas strings es «1111», que es 15 en forma decimal.Entrada: S1 = “11111”, S2 = “11111”, S3 = “11111”
Salida: 31
Explicación:
No hay otra forma de ordenar los dígitos. Por lo tanto, XOR es «11111», que es 31 en forma decimal.
Enfoque ingenuo: el enfoque más simple es generar todas las formas posibles de reorganizar S1 , S2 y S3 . Suponga que hay bits establecidos O1 , O2 y O3 en las strings S1 , S2 y S3 respectivamente. El número total de reordenamientos para verificar para obtener el valor máximo de XOR bit a bit es el siguiente:
Total de formas de reorganizar S1 = N C O1
Total de formas de reorganizar S2 = N C O2 Total de formas de reorganizar S3 = N C O3
Por lo tanto, el total de reordenamientos posibles para verificar = N C O1 * N C O2 * N C O3
Complejidad de tiempo: O((N!) 3 ), donde N es la longitud de las strings dadas.
Espacio Auxiliar: O(N)
Enfoque eficiente: la idea es encontrar una reorganización adecuada de S1 , S2 y S3 de modo que su valor Bitwise XOR se maximice mediante la programación dinámica . Los subproblemas se pueden almacenar en una tabla dp[][][][] donde dp[i][o1][o2][o3] almacena el valor máximo de XOR hasta la posición N-1 a partir del índice i , donde o1 es decir, o2 y o3 son el número de 1 s que quedan por colocar en las strings S1 , S2 y S3respectivamente.
Puede haber cuatro casos posibles en cualquier posición i de 0 a (N – 1) :
- Asigne 1 s a las tres strings
- Asigne 1 s a cualquiera de las dos strings
- Asigne 1 s a cualquiera de las strings.
- Asigne 0 s a todas las strings.
A partir de los posibles casos anteriores para cada posición, calcule el XOR bit a bit máximo que se puede obtener de las cuatro posibilidades:
Siga los pasos a continuación para resolver el problema:
- Inicialice una tabla dp[][][][] para almacenar el número de unos en S1 , S2 y S3 para las posiciones i de 0 a N-1 .
- Los estados de transición son los siguientes:
dp[i][o1][o2][o3] = max(dp(asignar 1 a las tres strings), dp(asignar 1 a cualquiera de las dos strings), dp(asignar 1 a cualquier string), dp( no asigne 1 a ninguna string)) donde,
i = posición actual
o1 = restantes para colocar en la string S1
o2 = restantes para colocar en la string S2
o3 = restantes para colocar en la string S3
- Resuelva los subproblemas para todos los casos usando la transición anterior e imprima el valor XOR máximo entre ellos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Dp table to store the sub-problems
int dp[20][20][20][20];
// Function to find the maximum XOR
// value after rearranging the digits
int maxXorValue(int i, string& s1,
string& s2, string& s3,
int ones1, int ones2,
int ones3, int n)
{
// Base Case
if (i >= n)
return 0;
// Return if already calculated
if (dp[i][ones1][ones2][ones3] != -1)
return dp[i][ones1][ones2][ones3];
int option1 = 0, option2 = 0,
option3 = 0, option4 = 0,
option5 = 0, option6 = 0,
option7 = 0, option8 = 0;
// Assigning 1's to all string at
// position 'i'.
if (ones1 > 0 && ones2 > 0
&& ones3 > 0)
// 2^(n-1-i) is the value
// added to the total
option1
= (1 << ((n - 1) - i))
+ maxXorValue(i + 1, s1,
s2, s3, ones1 - 1,
ones2 - 1,
ones3 - 1, n);
// Assigning 1's to strings 1 & 2
if (ones1 > 0 && ones2 > 0
&& (n - i > ones3))
option2
= 0
+ maxXorValue(i + 1, s1,
s2, s3, ones1 - 1,
ones2 - 1,
ones3, n);
// Assigning 1's to strings 2 & 3
if (ones2 > 0 && ones3 > 0
&& (n - i > ones1))
option3 = 0
+ maxXorValue(i + 1, s1,
s2, s3,
ones1,
ones2 - 1,
ones3 - 1, n);
// Assigning 1's to strings 3 & 1
if (ones3 > 0 && ones1 > 0
&& (n - i > ones2))
option4
= 0
+ maxXorValue(i + 1, s1,
s2, s3,
ones1 - 1,
ones2,
ones3 - 1, n);
// Assigning 1 to string 1
if (ones1 > 0 && (n - i > ones2)
&& (n - i > ones3))
option5 = (1 << ((n - 1) - i))
+ maxXorValue(i + 1, s1,
s2, s3,
ones1 - 1,
ones2,
ones3, n);
// Assigning 1 to string 2
if (ones2 > 0 && (n - i > ones3)
&& (n - i > ones1))
option6 = (1 << ((n - 1) - i))
+ maxXorValue(i + 1, s1,
s2, s3, ones1,
ones2 - 1,
ones3, n);
// Assigning 1 to string 3.
if (ones3 > 0 && (n - i > ones2)
&& (n - i > ones1))
option7 = (1 << ((n - 1) - i))
+ maxXorValue(i + 1, s1,
s2, s3, ones1,
ones2,
ones3 - 1, n);
// Assigning 0 to all the strings
if ((n - i > ones2) && (n - i > ones3)
&& (n - i > ones1))
option8 = 0
+ maxXorValue(i + 1, s1,
s2, s3,
ones1,
ones2,
ones3, n);
// Take the maximum amongst all of
// the above solutions
return dp[i][ones1][ones2][ones3]
= max(option1,
max(option2,
max(option3,
max(option4,
max(option5,
max(option6,
max(option7,
option8)))))));
}
// Function to get the count of ones
// in the string s
int onesCount(string& s)
{
int count = 0;
// Traverse the string
for (auto x : s) {
if (x == '1')
++count;
}
// Return the count
return count;
}
// Utility Function to find the maximum
// XOR value after rearranging the digits
void maxXORUtil(string s1, string s2,
string s3, int n)
{
// Find the count of ones in
// each of the strings
int ones1 = onesCount(s1);
int ones2 = onesCount(s2);
int ones3 = onesCount(s3);
// Initialize dp table with -1
memset(dp, -1, sizeof dp);
// Function Call
cout << maxXorValue(0, s1, s2, s3,
ones1, ones2,
ones3, n);
}
// Driver code
int main()
{
string s1 = "11110";
string s2 = "10101";
string s3 = "00111";
int n = s1.size();
// Function Call
maxXORUtil(s1, s2, s3, n);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
import java.lang.*;
class GFG{
// Dp table to store the sub-problems
static int[][][][] dp = new int[20][20][20][20];
// Function to find the maximum XOR
// value after rearranging the digits
static int maxXorValue(int i, String s1,
String s2, String s3,
int ones1, int ones2,
int ones3, int n)
{
// Base Case
if (i >= n)
return 0;
// Return if already calculated
if (dp[i][ones1][ones2][ones3] != -1)
return dp[i][ones1][ones2][ones3];
int option1 = 0, option2 = 0,
option3 = 0, option4 = 0,
option5 = 0, option6 = 0,
option7 = 0, option8 = 0;
// Assigning 1's to all string at
// position 'i'.
if (ones1 > 0 && ones2 > 0 &&
ones3 > 0)
// 2^(n-1-i) is the value
// added to the total
option1 = (1 << ((n - 1) - i)) +
maxXorValue(i + 1, s1, s2,
s3, ones1 - 1,
ones2 - 1,
ones3 - 1, n);
// Assigning 1's to strings 1 & 2
if (ones1 > 0 && ones2 > 0 &&
(n - i > ones3))
option2 = 0 + maxXorValue(i + 1, s1, s2,
s3, ones1 - 1,
ones2 - 1,
ones3, n);
// Assigning 1's to strings 2 & 3
if (ones2 > 0 && ones3 > 0 &&
(n - i > ones1))
option3 = 0 + maxXorValue(i + 1, s1, s2,
s3, ones1,
ones2 - 1,
ones3 - 1, n);
// Assigning 1's to strings 3 & 1
if (ones3 > 0 && ones1 > 0 &&
(n - i > ones2))
option4 = 0 + maxXorValue(i + 1, s1, s2,
s3, ones1 - 1,
ones2,
ones3 - 1, n);
// Assigning 1 to string 1
if (ones1 > 0 && (n - i > ones2) &&
(n - i > ones3))
option5 = (1 << ((n - 1) - i)) +
maxXorValue(i + 1, s1, s2,
s3, ones1 - 1,
ones2, ones3, n);
// Assigning 1 to string 2
if (ones2 > 0 && (n - i > ones3) &&
(n - i > ones1))
option6 = (1 << ((n - 1) - i)) +
maxXorValue(i + 1, s1,
s2, s3, ones1,
ones2 - 1,
ones3, n);
// Assigning 1 to string 3.
if (ones3 > 0 && (n - i > ones2) &&
(n - i > ones1))
option7 = (1 << ((n - 1) - i)) +
maxXorValue(i + 1, s1,
s2, s3, ones1,
ones2,
ones3 - 1, n);
// Assigning 0 to all the strings
if ((n - i > ones2) && (n - i > ones3) &&
(n - i > ones1))
option8 = 0 + maxXorValue(i + 1, s1,
s2, s3, ones1,
ones2, ones3, n);
// Take the maximum amongst all of
// the above solutions
return dp[i][ones1][ones2][ones3] =
Math.max(option1,
Math.max(option2,
Math.max(option3,
Math.max(option4,
Math.max(option5,
Math.max(option6,
Math.max(option7,
option8)))))));
}
// Function to get the count of ones
// in the string s
static int onesCount(String s)
{
int count = 0;
// Traverse the string
for(char x : s.toCharArray())
{
if (x == '1')
++count;
}
// Return the count
return count;
}
// Utility Function to find the maximum
// XOR value after rearranging the digits
static void maxXORUtil(String s1, String s2,
String s3, int n)
{
// Find the count of ones in
// each of the strings
int ones1 = onesCount(s1);
int ones2 = onesCount(s2);
int ones3 = onesCount(s3);
// Initialize dp table with -1
for(int[][][] i : dp)
for(int[][] j : i)
for(int[] k : j)
Arrays.fill(k, -1);
// Function Call
System.out.println(maxXorValue(0, s1, s2, s3,
ones1, ones2,
ones3, n));
}
// Driver code
public static void main (String[] args)
{
String s1 = "11110";
String s2 = "10101";
String s3 = "00111";
int n = s1.length();
// Function call
maxXORUtil(s1, s2, s3, n);
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the # above approach # Dp table to store the # sub-problems dp = [[[[-1 for x in range(20)] for y in range(20)] for z in range(20)] for p in range(20)] # Function to find the maximum # XOR value after rearranging # the digits def maxXorValue(i, s1, s2, s3, ones1, ones2, ones3, n): # Base Case if (i >= n): return 0 # Return if already #calculated if (dp[i][ones1][ones2][ones3] != -1): return dp[i][ones1][ones2][ones3] option1 = 0 option2 = 0 option3 = 0 option4 = 0 option5 = 0 option6 = 0 option7 = 0 option8 = 0 # Assigning 1's to all # string at position 'i'. if (ones1 > 0 and ones2 > 0 and ones3 > 0): # 2^(n-1-i) is the value # added to the total option1 = ((1 << ((n - 1) - i)) + maxXorValue(i + 1, s1, s2, s3, ones1 - 1, ones2 - 1, ones3 - 1, n)) # Assigning 1's to strings # 1 & 2 if (ones1 > 0 and ones2 > 0 and (n - i > ones3)): option2 = (0 + maxXorValue(i + 1, s1, s2, s3, ones1 - 1, ones2 - 1, ones3, n)) # Assigning 1's to strings # 2 & 3 if (ones2 > 0 and ones3 > 0 and (n - i > ones1)): option3 = (0 + maxXorValue(i + 1, s1, s2, s3, ones1, ones2 - 1, ones3 - 1, n)) # Assigning 1's to strings # 3 & 1 if (ones3 > 0 and ones1 > 0 and (n - i > ones2)): option4 = (0 + maxXorValue(i + 1, s1, s2, s3, ones1 - 1, ones2, ones3 - 1, n)) # Assigning 1 to string 1 if (ones1 > 0 and (n - i > ones2) and (n - i > ones3)): option5 = ((1 << ((n - 1) - i)) + maxXorValue(i + 1, s1, s2, s3, ones1 - 1, ones2, ones3, n)) # Assigning 1 to string 2 if (ones2 > 0 and (n - i > ones3) and (n - i > ones1)): option6 = ((1 << ((n - 1) - i)) + maxXorValue(i + 1, s1, s2, s3, ones1, ones2 - 1, ones3, n)) # Assigning 1 to string 3. if (ones3 > 0 and (n - i > ones2) and (n - i > ones1)): option7 = ((1 << ((n - 1) - i)) + maxXorValue(i + 1, s1, s2, s3, ones1, ones2, ones3 - 1, n)) # Assigning 0 to all the strings if ((n - i > ones2) and (n - i > ones3) and (n - i > ones1)): option8 = (0 + maxXorValue(i + 1, s1, s2, s3, ones1, ones2, ones3, n)) # Take the maximum amongst all of # the above solutions dp[i][ones1][ones2][ones3] = max(option1, max(option2, max(option3, max(option4, max(option5, max(option6, max(option7, option8))))))) return dp[i][ones1][ones2][ones3] # Function to get the count # of ones in the string s def onesCount(s): count = 0 # Traverse the string for x in s: if (x == '1'): count += 1 # Return the count return count # Utility Function to find # the maximum XOR value after # rearranging the digits def maxXORUtil(s1, s2, s3, n): # Find the count of ones in # each of the strings ones1 = onesCount(s1) ones2 = onesCount(s2) ones3 = onesCount(s3) global dp # Function Call print(maxXorValue(0, s1, s2, s3, ones1, ones2, ones3, n)) # Driver code if __name__ == "__main__": s1 = "11110" s2 = "10101" s3 = "00111" n = len(s1) # Function Call maxXORUtil(s1, s2, s3, n) # This code is contributed by Chitranayal
C#
// C# program for the
// above approach
using System;
class GFG{
// Dp table to store
// the sub-problems
static int[,,,] dp =
new int[20, 20,
20, 20];
// Function to find the
// maximum XOR value after
// rearranging the digits
static int maxXorValue(int i, String s1,
String s2, String s3,
int ones1, int ones2,
int ones3, int n)
{
// Base Case
if (i >= n)
return 0;
// Return if already calculated
if (dp[i, ones1,
ones2, ones3] != -1)
return dp[i, ones1,
ones2, ones3];
int option1 = 0, option2 = 0,
option3 = 0, option4 = 0,
option5 = 0, option6 = 0,
option7 = 0, option8 = 0;
// Assigning 1's to all
// string at position 'i'.
if (ones1 > 0 && ones2 > 0 &&
ones3 > 0)
// 2^(n-1-i) is the value
// added to the total
option1 = (1 << ((n - 1) - i)) +
maxXorValue(i + 1, s1,
s2, s3,
ones1 - 1,
ones2 - 1,
ones3 - 1, n);
// Assigning 1's to
// strings 1 & 2
if (ones1 > 0 && ones2 > 0 &&
(n - i > ones3))
option2 = 0 + maxXorValue(i + 1, s1, s2,
s3, ones1 - 1,
ones2 - 1,
ones3, n);
// Assigning 1's to strings 2 & 3
if (ones2 > 0 && ones3 > 0 &&
(n - i > ones1))
option3 = 0 + maxXorValue(i + 1, s1, s2,
s3, ones1,
ones2 - 1,
ones3 - 1, n);
// Assigning 1's to strings 3 & 1
if (ones3 > 0 && ones1 > 0 &&
(n - i > ones2))
option4 = 0 + maxXorValue(i + 1, s1, s2,
s3, ones1 - 1,
ones2,
ones3 - 1, n);
// Assigning 1 to string 1
if (ones1 > 0 && (n - i > ones2) &&
(n - i > ones3))
option5 = (1 << ((n - 1) - i)) +
maxXorValue(i + 1, s1,
s2,s3,
ones1 - 1,
ones2, ones3, n);
// Assigning 1 to string 2
if (ones2 > 0 && (n - i > ones3) &&
(n - i > ones1))
option6 = (1 << ((n - 1) - i)) +
maxXorValue(i + 1, s1,
s2, s3,
ones1,
ones2 - 1,
ones3, n);
// Assigning 1 to string 3.
if (ones3 > 0 && (n - i > ones2) &&
(n - i > ones1))
option7 = (1 << ((n - 1) - i)) +
maxXorValue(i + 1, s1,
s2, s3,
ones1,
ones2,
ones3 - 1, n);
// Assigning 0 to all the strings
if ((n - i > ones2) &&
(n - i > ones3) &&
(n - i > ones1))
option8 = 0 + maxXorValue(i + 1,
s1, s2,
s3, ones1,
ones2, ones3, n);
// Take the maximum amongst all of
// the above solutions
return dp[i, ones1,
ones2, ones3] = Math.Max(option1,
Math.Max(option2,
Math.Max(option3,
Math.Max(option4,
Math.Max(option5,
Math.Max(option6,
Math.Max(option7,
option8)))))));
}
// Function to get the count
// of ones in the string s
static int onesCount(String s)
{
int count = 0;
// Traverse the string
foreach(char x in s.ToCharArray())
{
if (x == '1')
++count;
}
// Return the count
return count;
}
// Utility Function to find the maximum
// XOR value after rearranging the digits
static void maxXORUtil(String s1, String s2,
String s3, int n)
{
// Find the count of ones in
// each of the strings
int ones1 = onesCount(s1);
int ones2 = onesCount(s2);
int ones3 = onesCount(s3);
// Initialize dp table with -1
for(int i = 0; i < 20; i++)
{
for(int j = 0; j < 20; j++)
{
for(int l = 0; l < 20; l++)
for(int k = 0; k < 20; k++)
dp[i, j, l, k] =- 1;
}
}
// Function Call
Console.WriteLine(maxXorValue(0, s1, s2, s3,
ones1, ones2,
ones3, n));
}
// Driver code
public static void Main(String[] args)
{
String s1 = "11110";
String s2 = "10101";
String s3 = "00111";
int n = s1.Length;
// Function call
maxXORUtil(s1, s2, s3, n);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Dp table to store the sub-problems
let dp = new Array(20);
for(let i = 0; i < 20; i++)
{
dp[i] = new Array(20);
for(let j = 0; j < 20; j++)
{
dp[i][j] = new Array(20);
for(let k = 0; k < 20; k++)
{
dp[i][j][k] = new Array(20);
for(let l = 0; l < 20; l++)
{
dp[i][j][k][l] = -1;
}
}
}
}
// Function to find the maximum XOR
// value after rearranging the digits
function maxXorValue(i, s1, s2, s3, ones1,
ones2, ones3, n)
{
// Base Case
if (i >= n)
return 0;
// Return if already calculated
if (dp[i][ones1][ones2][ones3] != -1)
return dp[i][ones1][ones2][ones3];
let option1 = 0, option2 = 0,
option3 = 0, option4 = 0,
option5 = 0, option6 = 0,
option7 = 0, option8 = 0;
// Assigning 1's to all string at
// position 'i'.
if (ones1 > 0 && ones2 > 0 &&
ones3 > 0)
// 2^(n-1-i) is the value
// added to the total
option1 = (1 << ((n - 1) - i)) +
maxXorValue(i + 1, s1, s2,
s3, ones1 - 1,
ones2 - 1,
ones3 - 1, n);
// Assigning 1's to strings 1 & 2
if (ones1 > 0 && ones2 > 0 &&
(n - i > ones3))
option2 = 0 + maxXorValue(i + 1, s1, s2,
s3, ones1 - 1,
ones2 - 1,
ones3, n);
// Assigning 1's to strings 2 & 3
if (ones2 > 0 && ones3 > 0 &&
(n - i > ones1))
option3 = 0 + maxXorValue(i + 1, s1, s2,
s3, ones1,
ones2 - 1,
ones3 - 1, n);
// Assigning 1's to strings 3 & 1
if (ones3 > 0 && ones1 > 0 &&
(n - i > ones2))
option4 = 0 + maxXorValue(i + 1, s1, s2,
s3, ones1 - 1,
ones2,
ones3 - 1, n);
// Assigning 1 to string 1
if (ones1 > 0 && (n - i > ones2) &&
(n - i > ones3))
option5 = (1 << ((n - 1) - i)) +
maxXorValue(i + 1, s1, s2,
s3, ones1 - 1,
ones2, ones3, n);
// Assigning 1 to string 2
if (ones2 > 0 && (n - i > ones3) &&
(n - i > ones1))
option6 = (1 << ((n - 1) - i)) +
maxXorValue(i + 1, s1,
s2, s3, ones1,
ones2 - 1,
ones3, n);
// Assigning 1 to string 3.
if (ones3 > 0 && (n - i > ones2) &&
(n - i > ones1))
option7 = (1 << ((n - 1) - i)) +
maxXorValue(i + 1, s1,
s2, s3, ones1,
ones2,
ones3 - 1, n);
// Assigning 0 to all the strings
if ((n - i > ones2) && (n - i > ones3) &&
(n - i > ones1))
option8 = 0 + maxXorValue(i + 1, s1,
s2, s3, ones1,
ones2, ones3, n);
// Take the maximum amongst all of
// the above solutions
return dp[i][ones1][ones2][ones3] =
Math.max(option1,
Math.max(option2,
Math.max(option3,
Math.max(option4,
Math.max(option5,
Math.max(option6,
Math.max(option7,
option8)))))));
}
// Function to get the count of ones
// in the string s
function onesCount(s)
{
let count = 0;
// Traverse the string
for(let x = 0; x < s.length; x++)
{
if (s[x] == '1')
++count;
}
// Return the count
return count;
}
// Utility Function to find the maximum
// XOR value after rearranging the digits
function maxXORUtil(s1, s2, s3, n)
{
// Find the count of ones in
// each of the strings
let ones1 = onesCount(s1);
let ones2 = onesCount(s2);
let ones3 = onesCount(s3);
// Function Call
document.write(maxXorValue(0, s1, s2, s3,
ones1, ones2,
ones3, n));
}
// Driver code
let s1 = "11110";
let s2 = "10101";
let s3 = "00111";
let n = s1.length;
// Function call
maxXORUtil(s1, s2, s3, n);
// This code is contributed by avanitrachhadiya2155
</script>
Producción
30
Complejidad de Tiempo: O(N 4 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA