Проверьте, можно ли сделать все биты одинаковыми с помощью одного переворота

Опубликовано: 20 Января, 2022

Учитывая двоичную строку, найдите, можно ли сделать все ее цифры равными (либо все нули, либо все единицы), перевернув ровно один бит.

 Ввод: 101
Выход: Да
Объяснение: В 101 0 можно перевернуть
             сделать все 1

Ввод: 11
Выход: Нет
Пояснение: какую бы цифру вы ни выбрали 
  переверните, вы не получите нужную строку.

Ввод: 1
Выход: Да
Объяснение: Мы можем перевернуть 1, чтобы все нули
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Метод 1 (подсчет нулей и единиц)
Если все цифры строки можно сделать идентичными, выполнив ровно один переворот, это означает, что в строке все цифры равны друг другу, кроме этой цифры, которую нужно перевернуть, и эта цифра должна отличаться от всех других цифр строки. . Значение этой цифры может быть либо нулем, либо единицей. Следовательно, в этой строке будет либо ровно одна цифра, равная нулю, а все остальные цифры, равные единице, либо ровно одна цифра, равная единице, а все остальные цифры будут равны нулю.
Следовательно, нам нужно только проверить, есть ли в строке ровно одна цифра, равная нулю / единице, и если да, то ответ - да; в противном случае ответ отрицательный.

Below is the implementation of above idea.  

C++

// C++ program to check if a sinle 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 ") : printf("No ");
    return 0;
}

Java

// 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

Python3

# python program to check if a sinle
# 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 ")
else:
    print("No ")
 
# This code is contributed by Sam007.

C#

// 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
 
// PHP program to check if a sinle 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 " ;
    else echo "No ";
    return 0;
?>

Javascript

<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>

Выход:

 да

Сложность по времени: O (n), где n - длина строки.

Метод 2 (подсчет нулей и единиц)
Идея состоит в том, чтобы вычислить сумму всех битов. Если сумма равна n-1 или 1, тогда вывод будет истинным, иначе ложным. Это решение не требует сравнения в цикле.

Below is the implementation of above idea.  

C++

// 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 ") : printf("No ");
 
    return 0;
}

Java

/*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

Python3

# 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

C#

/*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

<?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 ";
    else
        echo "No ";
 
// This code is contributed by aj_36
?>

Javascript

<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
 
Алгоритмы

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Наихудший, средний и лучший анализ алгоритмов
4 Января, 2023
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Что такое логарифмическая временная сложность? Полное руководство
12 Декабря, 2022
Amazon SDE Sheet: вопросы и ответы на собеседовании
12 Декабря, 2022