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

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.