Dadas dos strings de números binarios 
y 
de longitud 
. Encuentre el número de formas de intercambiar dos bits en s1 (solo s1 no s2) para que se cambien los bits OR de estos dos números s1 y s2 .
Nota: La longitud de ambas strings debe ser igual, puede tomar ceros a la izquierda en caso de longitud diferente.
Ejemplo:
Input: s1 = "01011", s2 = "11001" Output: 4 Explanation: You can swap the bit of s1 at indexed: (1, 4), (2, 3), (3, 4) and (3, 5) there are 4 ways possible. Input: s1 = "011000", s2 = "010011" Output: 6
Enfoque: inicialice un resultado variable como cero que almacene varias formas de intercambiar bits de s1 para que cambie el OR bit a bit de s1 y s2. Inicialice cuatro variables, digamos 
, 
, 
y 
como cero.
Atraviese ambas strings desde el lado izquierdo y verifique las siguientes condiciones para incrementar los valores de la
variable declarada anteriormente:
- Si el bit actual de s1 y s2 es cero, incremente c.
- Si el bit actual de s2 es cero y s1 es uno, incremente d.
- Si el bit actual de s2 es uno y s1 es cero, incremente a.
- Si el bit actual de s1 y s2 es uno, incremente b.
Actualice el resultado por (a*d) + (b*c) + (c*d) y devuelva el resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find no of ways
// to swap bits of s1 so that
// bitwise OR of s1 and s2 changes
#include <iostream>
using namespace std;
// Function to find number of ways
int countWays(string s1, string s2, int n)
{
int a, b, c, d;
a = b = c = d = 0;
// initialise result that store
// No. of swaps required
int result = 0;
// Traverse both strings and check
// the bits as explained
for (int i = 0; i < n; i++) {
if (s2[i] == '0') {
if (s1[i] == '0') {
c++;
}
else {
d++;
}
}
else {
if (s1[i] == '0') {
a++;
}
else {
b++;
}
}
}
// calculate result
result = a * d + b * c + c * d;
return result;
}
// Driver code
int main()
{
int n = 5;
string s1 = "01011";
string s2 = "11001";
cout << countWays(s1, s2, n);
return 0;
}
Java
// Java program to find no of ways
// to swap bits of s1 so that
// bitwise OR of s1 and s2 changes
import java.io.*;
class GFG {
// Function to find number of ways
static int countWays(String s1, String s2, int n)
{
int a, b, c, d;
a = b = c = d = 0;
// initialise result that store
// No. of swaps required
int result = 0;
// Traverse both strings and check
// the bits as explained
for (int i = 0; i < n; i++) {
if (s2.charAt(i) == '0') {
if (s1.charAt(i) == '0') {
c++;
}
else {
d++;
}
}
else {
if (s1.charAt(i) == '0') {
a++;
}
else {
b++;
}
}
}
// calculate result
result = a * d + b * c + c * d;
return result;
}
// Driver code
public static void main (String[] args) {
int n = 5;
String s1 = "01011";
String s2 = "11001";
System.out.println(countWays(s1, s2, n));
}
}
// This code is contributed by shs..
Python3
# Python 3 program to find no of ways # to swap bits of s1 so that # bitwise OR of s1 and s2 changes # Function to find number of ways def countWays(s1, s2, n): a = b = c = d = 0 # initialise result that store # No. of swaps required result = 0; # Traverse both strings and check # the bits as explained for i in range(0, n, 1): if (s2[i] == '0'): if (s1[i] == '0'): c += 1; else: d += 1 else: if (s1[i] == '0'): a += 1 else: b += 1 # calculate result result = a * d + b * c + c * d return result # Driver code if __name__ == '__main__': n = 5 s1 = "01011" s2 = "11001" print(countWays(s1, s2, n)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find no of ways
// to swap bits of s1 so that
// bitwise OR of s1 and s2 changes
using System;
class GFG {
// Function to find number of ways
static int countWays(string s1, string s2, int n)
{
int a, b, c, d;
a = b = c = d = 0;
// initialise result that store
// No. of swaps required
int result = 0;
// Traverse both strings and check
// the bits as explained
for (int i = 0; i < n; i++) {
if (s2[i] == '0') {
if (s1[i] == '0') {
c++;
}
else {
d++;
}
}
else {
if (s1[i] == '0') {
a++;
}
else {
b++;
}
}
}
// calculate result
result = a * d + b * c + c * d;
return result;
}
// Driver code
public static void Main () {
int n = 5;
string s1 = "01011";
string s2 = "11001";
Console.WriteLine(countWays(s1, s2, n));
}
}
// This code is contributed by shs..
PHP
<?php
// PHP program to find no of ways
// to swap bits of s1 so that
// bitwise OR of s1 and s2 changes
// Function to find number of ways
function countWays($s1, $s2, $n)
{
$a = $b = $c = $d = 0;
// initialise result that store
// No. of swaps required
$result = 0;
// Traverse both strings and check
// the bits as explained
for ($i = 0; $i < $n; $i++)
{
if ($s2[$i] == '0')
{
if ($s1[$i] == '0')
{
$c++;
}
else
{
$d++;
}
}
else
{
if ($s1[$i] == '0')
{
$a++;
}
else
{
$b++;
}
}
}
// calculate result
$result = $a * $d + $b *
$c + $c * $d;
return $result;
}
// Driver code
$n = 5;
$s1 = "01011";
$s2 = "11001";
echo countWays($s1, $s2, $n);
// This code is contributed by ajit
?>
Javascript
<script>
// javascript program to find no of ways
// to swap bits of s1 so that
// bitwise OR of s1 and s2 changes
// Function to find number of ways
function countWays(s1, s2 , n)
{
var a, b, c, d;
a = b = c = d = 0;
// initialise result that store
// No. of swaps required
var result = 0;
// Traverse both strings and check
// the bits as explained
for (i = 0; i < n; i++) {
if (s2.charAt(i) == '0') {
if (s1.charAt(i) == '0') {
c++;
}
else {
d++;
}
}
else {
if (s1.charAt(i) == '0') {
a++;
}
else {
b++;
}
}
}
// calculate result
result = a * d + b * c + c * d;
return result;
}
// Driver code
var n = 5;
var s1 = "01011";
var s2 = "11001";
document.write(countWays(s1, s2, n));
// This code is contributed by Princi Singh
</script>
Producción
4
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)