Dadas dos strings binarias S1 y S2 , ambas de longitud N , la tarea es contar el número de valores diferentes de Bitwise OR que no sean Bitwise OR de las strings originales S1 y S2 intercambiando exactamente un par de caracteres de la string S1 .
Ejemplos:
Entrada: S1 = “1100”, S2 = “0011”
Salida: 4
Explicación: OR bit a bit de S1 y S2, si no se realiza intercambio es “1111”.
A continuación se muestra el intercambio de caracteres realizado para obtener los diferentes valores de Bitwise OR:
- Si se intercambian los caracteres en el índice 0 y 2 , entonces la string S1 se modifica a «0110» . Ahora, el OR bit a bit de ambas strings es «0111».
- Si los caracteres en el índice 0 y 3 se intercambian , la string S1 se modifica a «0101». Ahora, el OR bit a bit de ambas strings es «0111».
- Si se intercambian los caracteres en el 1er y 2do índice, entonces la string S1 se modifica a «1010». Ahora, el OR bit a bit de ambas strings es «1011».
- Si se intercambian los caracteres en el 1er y 3er índice , entonces la string S1 se modifica a «1001». Ahora, el OR bit a bit de ambas strings es «1011».
Después de los pasos anteriores, todos los OR bit a bit son diferentes del OR bit a bit de la string original. Por lo tanto, la cuenta total es 4.
Entrada: S1 = “01001”, S2 = “11011”
Salida: 2
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Si se intercambia el mismo carácter en la string S1 , entonces no afectará el OR bit a bit .
- Si los diferentes caracteres se intercambian en la string S1 , digamos S1[i] = ‘0’ y S2[j] = ‘1’, entonces el OR bit a bit del valor se cambia según las siguientes reglas:
- Si S2[i] = ‘0’ y S2[j] = ‘0’ .
- Si S2[i] = ‘1’ y S2[j] = ‘0’ .
- Si S2[i] = ‘0’ y S2[j] = ‘1’ .
A partir de las observaciones anteriores, siga los pasos a continuación para resolver el problema:
- Inicialice cuatro variables, digamos t00 , t10 , t11 , t01 que almacena el número de índices i tal que S1[i] = ‘0’ y S2[i] = ‘0’ , S1[i] = ‘1’ y S2[ i] = ‘0’ , S1[i] = ‘1’ y S2[i] = ‘1’ , y S1[i] = ‘0’ y S2[i] = ‘1’ respectivamente.
- Atraviese las strings dadas S1 y S2 e incremente el valor de t00 , t10 , t11 , t01 según lo siguiente:
- Si S1[i] = ‘0’ y S2[i] =’0′ , aumente el valor de t00 en 1 .
- Si S1[i] = ‘1’ y S2[i] = ‘0’ , entonces incremente el valor de t10 en 1 .
- Si S1[i] = ‘1’ y S2[i] = ‘1’ , aumente el valor de t11 en 1 .
- Si S1[i] = ‘0’ y S2[i] = ‘1’ , entonces incremente el valor de t01 en 1 .
- Después de completar los pasos anteriores, imprima el valor de t00 * t10 + t01 * t10 + t00 * t11 como el número resultante de intercambios necesarios que tengan un OR bit a bit diferente del OR bit a bit original.
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;
// Function to find the number of ways
// to obtain different Bitwise OR
void differentBitwiseOR(string s1,
string s2)
{
int n = s1.size();
// Stores the count of pairs t00,
// t10, t01, t11
int t00 = 0, t10 = 0, t01 = 0, t11 = 0;
// Traverse the characters of
// the string S1 and S2
for (int i = 0; i < n; i++) {
// Count the pair (0, 0)
if (s1[i] == '0'
&& s2[i] == '0') {
t00++;
}
// Count the pair (1, 0)
if (s1[i] == '1'
&& s2[i] == '0') {
t10++;
}
// Count the pair (1, 1)
if (s1[i] == '1'
&& s2[i] == '1') {
t11++;
}
// Count the pair (0, 1)
if (s1[i] == '0'
&& s2[i] == '1') {
t01++;
}
}
// Number of ways to calculate the
// different bitwise OR
int ans = t00 * t10 + t01 * t10
+ t00 * t11;
// Print the result
cout << ans;
}
// Driver Code
int main()
{
string S1 = "01001";
string S2 = "11011";
differentBitwiseOR(S1, S2);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the number of ways
// to obtain different Bitwise OR
static void differentBitwiseOR(String s1, String s2)
{
int n = s1.length();
// Stores the count of pairs t00,
// t10, t01, t11
int t00 = 0, t10 = 0, t01 = 0, t11 = 0;
// Traverse the characters of
// the string S1 and S2
for(int i = 0; i < n; i++)
{
// Count the pair (0, 0)
if (s1.charAt(i) == '0' &&
s2.charAt(i) == '0')
{
t00++;
}
// Count the pair (1, 0)
if (s1.charAt(i) == '1' &&
s2.charAt(i) == '0')
{
t10++;
}
// Count the pair (1, 1)
if (s1.charAt(i) == '1' &&
s2.charAt(i) == '1')
{
t11++;
}
// Count the pair (0, 1)
if (s1.charAt(i) == '0' &&
s2.charAt(i) == '1')
{
t01++;
}
}
// Number of ways to calculate the
// different bitwise OR
int ans = t00 * t10 + t01 * t10 + t00 * t11;
// Print the result
System.out.print(ans);
}
// Driver Code
public static void main(String[] args)
{
String S1 = "01001";
String S2 = "11011";
differentBitwiseOR(S1, S2);
}
}
// This code is contributed by subhammahato348
Python3
# Python program for the above approach # Function to find the number of ways # to obtain different Bitwise OR def differentBitwiseOR(s1, s2): n = len(s1) # Stores the count of pairs t00, # t10, t01, t11 t00 = 0 t10 = 0 t01 = 0 t11 = 0 # Traverse the characters of # the string S1 and S2 for i in range(n): # Count the pair (0, 0) if (s1[i] == '0' and s2[i] == '0'): t00 += 1 # Count the pair (1, 0) if (s1[i] == '1' and s2[i] == '0'): t10 += 1 # Count the pair (1, 1) if (s1[i] == '1' and s2[i] == '1'): t11 += 1 # Count the pair (0, 1) if (s1[i] == '0' and s2[i] == '1'): t01 += 1 # Number of ways to calculate the # different bitwise OR ans = t00 * t10 + t01 * t10 + t00 * t11 # Print the result print(ans) # Driver Code S1 = "01001" S2 = "11011" differentBitwiseOR(S1, S2) # This code is contributed by _saurabh_jaiswal
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the number of ways
// to obtain different Bitwise OR
static void differentBitwiseOR(String s1,
String s2)
{
int n = s1.Length;
// Stores the count of pairs t00,
// t10, t01, t11
int t00 = 0, t10 = 0, t01 = 0, t11 = 0;
// Traverse the characters of
// the string S1 and S2
for(int i = 0; i < n; i++)
{
// Count the pair (0, 0)
if (s1[i] == '0' && s2[i] == '0')
{
t00++;
}
// Count the pair (1, 0)
if (s1[i] == '1' && s2[i] == '0')
{
t10++;
}
// Count the pair (1, 1)
if (s1[i] == '1' && s2[i] == '1')
{
t11++;
}
// Count the pair (0, 1)
if (s1[i] == '0' && s2[i] == '1')
{
t01++;
}
}
// Number of ways to calculate the
// different bitwise OR
int ans = t00 * t10 + t01 * t10 + t00 * t11;
// Print the result
Console.Write(ans);
}
// Driver Code
public static void Main()
{
String S1 = "01001";
String S2 = "11011";
differentBitwiseOR(S1, S2);
}
}
// This code is contributed by subhammahato348
Javascript
<script>
// JavaScript program for the above approach
// Function to find the number of ways
// to obtain different Bitwise OR
function differentBitwiseOR(s1, s2) {
let n = s1.length;
// Stores the count of pairs t00,
// t10, t01, t11
let t00 = 0, t10 = 0, t01 = 0, t11 = 0;
// Traverse the characters of
// the string S1 and S2
for (let i = 0; i < n; i++) {
// Count the pair (0, 0)
if (s1[i] == '0'
&& s2[i] == '0') {
t00++;
}
// Count the pair (1, 0)
if (s1[i] == '1'
&& s2[i] == '0') {
t10++;
}
// Count the pair (1, 1)
if (s1[i] == '1'
&& s2[i] == '1') {
t11++;
}
// Count the pair (0, 1)
if (s1[i] == '0'
&& s2[i] == '1') {
t01++;
}
}
// Number of ways to calculate the
// different bitwise OR
let ans = t00 * t10 + t01 * t10
+ t00 * t11;
// Print the result
document.write(ans);
}
// Driver Code
let S1 = "01001";
let S2 = "11011";
differentBitwiseOR(S1, S2);
// This code is contributed by Potta Lokesh
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ujjwalgoel1103 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA