Compruebe si todos los bits se pueden hacer iguales con un solo giro

Dada una string binaria, encuentre si es posible hacer que todos sus dígitos sean iguales (ya sea todos 0 o todos 1) cambiando exactamente un bit. 

Input: 101
Output: Yes
Explanation: In 101, the 0 can be flipped
             to make it all 1

Input: 11
Output: No
Explanation: No matter whichever digit you 
  flip, you will not get the desired string.

Input: 1
Output: Yes
Explanation: We can flip 1, to make all 0's

Método 1 (Contar 0 y 1) 
Si todos los dígitos de una string se pueden hacer idénticos haciendo exactamente un giro, eso significa que la string tiene todos sus dígitos iguales excepto este dígito que debe invertirse, y este dígito debe ser diferente a todos los demás dígitos de la string. El valor de este dígito puede ser cero o uno. Por lo tanto, esta string tendrá exactamente un dígito igual a cero y todos los demás dígitos iguales a uno, o exactamente un dígito igual a uno y todos los demás dígitos iguales a cero.
Por lo tanto, solo debemos verificar si la string tiene exactamente un dígito igual a cero/uno, y si es así, la respuesta es sí; de lo contrario, la respuesta es no.

A continuación se muestra la implementación de la idea anterior.  

// C++ program to check if a single bit can
// be flipped tp make all ones
#include <bits/stdc++.h>
using namespace std;
 
// This function returns true if we can
// bits same in given binary string str.
bool canMakeAllSame(string str)
{
    int zeros = 0, ones = 0;
 
    // Traverse through given string and
    // count numbers of 0's and 1's
    for (char ch : str)
        (ch == '0') ? ++zeros : ++ones;
 
    // Return true if any of the two counts
    // is 1
    return (zeros == 1 || ones == 1);
}
 
// Driver code
int main()
{
    canMakeAllSame("101") ? printf("Yes\n") : printf("No\n");
    return 0;
}

// Java program to check if a single bit can
// be flipped to make all ones
public class GFG {
 
    // This function returns true if we can
    // bits same in given binary string str.
    static boolean canMakeAllSame(String str)
    {
        int zeros = 0, ones = 0;
 
        // Traverse through given string and
        // count numbers of 0's and 1's
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if (ch == '0')
                ++zeros;
            else
                ++ones;
        }
 
        // Return true if any of the two counts
        // is 1
        return (zeros == 1 || ones == 1);
    }
 
    // Driver code
    public static void main(String args[])
    {
        System.out.println(canMakeAllSame("101") ? "Yes" : "No");
    }
}
// This code is contributed by Sumit Ghosh

# python program to check if a single
# bit can be flipped tp make all ones
 
# This function returns true if we can
# bits same in given binary string str.
def canMakeAllSame(str):
    zeros = 0
    ones = 0
 
    # Traverse through given string and
    # count numbers of 0's and 1's
    for i in range(0, len(str)):
        ch = str[i];
        if (ch == '0'):
            zeros = zeros + 1
        else:
            ones = ones + 1
 
    # Return true if any of the two
    # counts is 1
    return (zeros == 1 or ones == 1);
 
# Driver code
if(canMakeAllSame("101")):
    print("Yes\n")
else:
    print("No\n")
 
# This code is contributed by Sam007.

// C# program to check if a single bit can
// be flipped to make all ones
using System;
 
class GFG {
     
    // This function returns true if we can
    // bits same in given binary string str.
    static bool canMakeAllSame(string str)
    {
        int zeros = 0, ones = 0;
 
        // Traverse through given string and
        // count numbers of 0's and 1's
        for (int i = 0; i < str.Length; i++) {
            char ch = str[i];
            if (ch == '0')
                ++zeros;
            else
                ++ones;
        }
 
        // Return true if any of the two counts
        // is 1
        return (zeros == 1 || ones == 1);
    }
 
    // Driver code
    public static void Main()
    {
        Console.WriteLine(canMakeAllSame("101") ? "Yes" : "No");
    }
}
 
// This code is contributed by Sam007

<?php
 
// PHP program to check if a single bit can
// be flipped tp make all ones
  
// This function returns true if we can
// bits same in given binary string str.
function canMakeAllSame($str)
{
    $zeros = 0;
    $ones = 0;
  
    // Traverse through given string and
    // count numbers of 0's and 1's
     
    for($i=0;$i<strlen($str);$i++)
    {
        $ch = $str[$i];
        if ($ch == '0')
            ++$zeros ;
        else
            ++$ones;
    }
    // Return true if any of the two counts
    // is 1
    return ($zeros == 1 || $ones == 1);
}
  
// Driver code
 
    if (canMakeAllSame("101") )
       echo "Yes\n" ;
    else echo "No\n";
    return 0;
?>

<script>
// Javascript program to check if a single bit can
// be flipped to make all ones
     
    // This function returns true if we can
    // bits same in given binary string str.
    function canMakeAllSame(str)
    {
        let zeros = 0, ones = 0;
   
        // Traverse through given string and
        // count numbers of 0's and 1's
        for (let i = 0; i < str.length; i++) {
            let ch = str[i];
            if (ch == '0')
                ++zeros;
            else
                ++ones;
        }
   
        // Return true if any of the two counts
        // is 1
        return (zeros == 1 || ones == 1);
    }
     
    // Driver code
    document.write(canMakeAllSame("101") ? "Yes" : "No");
     
    // This code is contributed by rag2127
</script>

Producción: 

Yes

Complejidad temporal: O(n) donde n es la longitud de la string.

Espacio Auxiliar: O(1)

Método 2 (Contar 0 y 1) 
La idea es calcular la suma de todos los bits. Si la suma es n-1 o 1, la salida es verdadera, de lo contrario, falsa. Esta solución no requiere una comparación en un bucle.

A continuación se muestra la implementación de la idea anterior.  

// Check if all bits can be made same by single flip
// Idea is to add the integer value all the elements
// in the given string.
// If the sum is 1 it indicates that there is
// only single '1' in the string.
// If the sum is 0 it indicates that there is only
// single '0' in the string.
// It takes O(n) time.
 
#include <bits/stdc++.h>
using namespace std;
 
bool isOneFlip(string str)
{
    int sum = 0;
    int n = str.length();
 
    // Traverse through given string and
    // count the total sum of numbers
    for (int i = 0; i < n; i++)
        sum += str[i] - '0';
 
    // Return true if any of the two counts
    // is 1
    return (sum == n - 1 || sum == 1);
}
 
// Main function
int main()
{
    isOneFlip("101111111111") ? printf("Yes\n") : printf("No\n");
 
    return 0;
}

/*Check if all bits can be made same by single
flip. Idea is to add the integer value all the
elements in the given string.
If the sum is 1 it indicates that there is
   only single '1' in the string.
If the sum is 0 it indicates that there is only
   single '0' in the string.
It takes O(n) time.*/
public class GFG {
 
    static boolean isOneFlip(String str)
    {
        int sum = 0;
        int n = str.length();
 
        // Traverse through given string and
        // count the total sum of numbers
        for (int i = 0; i < n; i++)
            sum += str.charAt(i) - '0';
 
        // Return true if any of the two counts
        // is 1
        return (sum == n - 1 || sum == 1);
    }
 
    // Main function
    public static void main(String args[])
    {
        System.out.println(isOneFlip("101111111111") ? "Yes" : "No");
    }
}
// This code is contributed by Sumit Ghosh

# Check if all bits can be made same
# by single flip Idea is to add the
# integer value all the elements in
# the given string. If the sum is 1
# it indicates that there is only
# single '1' in the string. If the
# sum is 0 it indicates that there
# is only single '0' in the string.
# It takes O(n) time.
 
def isOneFlip(str):
 
    sum = 0
    n = len(str)
 
    # Traverse through given string
    # and count the total sum of
    # numbers
    for i in range( 0, n ):
        sum += int(str[i]) - int('0')
 
    # Return true if any of the two
    # counts is 1
    return (sum == n - 1 or sum == 1)
 
# Main function
(print("Yes") if isOneFlip("101111111111")
                        else print("No"))
 
# This code is contributed by Smitha

/*Check if all bits can be made same by single
  flip. Idea is to add the integer value all the
  elements in the given string.
  If the sum is 1 it indicates that there is
  only single '1' in the string.
  If the sum is 0 it indicates that there is only
  single '0' in the string.
  It takes O(n) time.*/
using System;
 
class GFG {
     
    static bool isOneFlip(string str)
    {
        int sum = 0;
        int n = str.Length;
 
        // Traverse through given string and
        // count the total sum of numbers
        for (int i = 0; i < n; i++)
            sum += str[i] - '0';
 
        // Return true if any of the two counts
        // is 1
        return (sum == n - 1 || sum == 1);
    }
 
    // Driver code
    public static void Main()
    {
        Console.WriteLine(isOneFlip("101111111111") ? "Yes" : "No");
    }
}
 
// This code is contributed by Sam007

<?php
// Check if all bits can be made same by
// single flip Idea is to add the integer
// value all the elements in the given
// string. If the sum is 1 it indicates
// that there is only single '1' in the
// string. If the sum is 0 it indicates
// that there is only single '0' in the
// string. It takes O(n) time.
 
function isOneFlip($str)
{
    $sum = 0;
    $n = strlen($str);
 
    // Traverse through given string and
    // count the total sum of numbers
    for ( $i = 0; $i < $n; $i++)
        $sum += $str[$i] - '0';
 
    // Return true if any of the two counts
    // is 1
    return ($sum == $n - 1 || $sum == 1);
}
 
// Main function
    if(isOneFlip("101111111111") )
        echo "Yes\n";
    else
        echo "No\n";
 
// This code is contributed by aj_36
?>

<script>
 
/*Check if all bits can be made same by single
flip. Idea is to add the integer value all the
elements in the given string.
If the sum is 1 it indicates that there is
   only single '1' in the string.
If the sum is 0 it indicates that there is only
   single '0' in the string.
It takes O(n) time.*/
function isOneFlip(str)
{
    let sum = 0;
    let n = str.length;
 
    // Traverse through given string and
    // count the total sum of numbers
    for(let i = 0; i < n; i++)
        sum += str[i] - '0';
 
    // Return true if any of the two counts
    // is 1
    return (sum == n - 1 || sum == 1);
}
 
// Driver code
document.write(isOneFlip("101111111111") ?
               "Yes" : "No");
 
// This code is contributed by avanitrachhadiya2155
 
</script>

Producción: 

Yes

Complejidad de tiempo: O(N)
Espacio auxiliar: O(1) 
Gracias a Sourabh Gavhale por sugerir esta solución

Este artículo es una contribución de Aarti_Rathi y Subrata Ghosh . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.