Рубрики

Количество способов разбить двоичное число таким образом, чтобы каждая часть делилась на 2

Для заданной двоичной строки S задача состоит в том, чтобы найти количество способов разбить ее на части так, чтобы каждая часть делилась на 2 .

Примеры:

Input: S = “100”
Output: 2
There are two ways to split the string:
{“10”, “0”} and {“100”}

Input: S = “110”
Output: 1

Подход: одно наблюдение состоит в том, что строку можно разбить только после 0 . Таким образом, посчитать количество нулей в строке. Давайте назовем этот счет c_zero . Предполагая случай, когда строка четная, для каждого 0, кроме самого правого, есть два варианта, т.е. либо обрезать строку после этого нуля, либо нет. Таким образом, окончательный ответ становится равным 2 (c_zero — 1) для четных строк.
Случай, когда строка не может быть разделена — это случай, когда она заканчивается на 1 . Таким образом, для нечетных строк ответ всегда будет нулевым, так как последняя разделенная часть всегда будет нечетной.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
#define maxN 20
#define maxM 64

  
// Функция для возврата необходимого количества

int cntSplits(string s)

{

    // Если разделение невозможно

    if (s[s.size() - 1] == '1')

        return 0;

  

    // Для сохранения количества нулей

    int c_zero = 0;

  

    // Подсчет количества нулей

    for (int i = 0; i < s.size(); i++)

        c_zero += (s[i] == '0');

  

    // Возвращаем окончательный ответ

    return (int)pow(2, c_zero - 1);

}

  
// Код драйвера

int main()

{

    string s = "10010";

  

    cout << cntSplits(s);

  

    return 0;

}

Джава

// Java реализация подхода

class GFG 

{

  

static int maxN = 20;

static int maxM = 64;

  
// Функция для возврата необходимого количества

static int cntSplits(String s)

{

    // Если разделение невозможно

    if (s.charAt(s.length() - 1) == '1')

        return 0;

  

    // Для сохранения количества нулей

    int c_zero = 0;

  

    // Подсчет количества нулей

    for (int i = 0; i < s.length(); i++)

        c_zero += (s.charAt(i) == '0') ? 1 : 0;

  

    // Возвращаем окончательный ответ

    return (int)Math.pow(2, c_zero - 1);

}

  
// Код драйвера

public static void main(String []args)

{

    String s = "10010";

  

    System.out.println(cntSplits(s));

}
}

  
// Этот код предоставлен PrinciRaj1992

python3

# Python3 реализация подхода

  
# Функция для возврата необходимого количества

def cntSplits(s) :

  

    # Если разделение невозможно

    if (s[len(s) - 1] == '1') :

        return 0

  

    # Хранить количество нулей

    c_zero = 0

  

    # Подсчет количества нулей

    for i in range(len(s)) :

        c_zero += (s[i] == '0'); 

  

    # Вернуть окончательный ответ

    return int(pow(2, c_zero - 1)); 

  
# Код драйвера

if __name__ == "__main__"

  

    s = "10010"

  

    print(cntSplits(s));

      
# Этот код предоставлен AnkitRai01

C #

// C # реализация подхода

using System;

                      

class GFG 

{

  

static int maxN = 20;

static int maxM = 64;

  
// Функция для возврата необходимого количества

static int cntSplits(String s)

{

    // Если разделение невозможно

    if (s[s.Length - 1] == '1')

        return 0;

  

    // Для сохранения количества нулей

    int c_zero = 0;

  

    // Подсчет количества нулей

    for (int i = 0; i < s.Length; i++)

        c_zero += (s[i] == '0') ? 1 : 0;

  

    // Возвращаем окончательный ответ

    return (int)Math.Pow(2, c_zero - 1);

}

  
// Код драйвера

public static void Main(String []args)

{

    String s = "10010";

  

    Console.WriteLine(cntSplits(s));

}
}

  
// Этот код предоставлен 29AjayKumar

Выход:

4

Рекомендуемые посты:

Количество способов разбить двоичное число таким образом, чтобы каждая часть делилась на 2

0.00 (0%) 0 votes