Рубрики

Максимальное количество разбиений двоичного числа

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

Примеры:

Input: S = “100”
Output: 2
The splits are as follows:
“10” ans “0”.

Input: S = “110”
Output: 1

Подход: эту проблему можно решить жадно, начните с левого конца и поместите разрез в индекс j так , чтобы j был наименьшим индексом, для которого подстрока до j делится на 2 . Теперь продолжите этот шаг с остальной оставшейся строкой. Также известно, что любое двоичное число, заканчивающееся на 0 , делится на 2 . Таким образом, поместите разрез после каждого нуля, и ответ будет равен числу нулей в строке. Единственный случай, когда ответ невозможен, — это когда заданная строка нечетная, т.е. независимо от того, как сделаны надрезы на строке, последняя разделенная часть всегда будет нечетной.

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

C ++

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

using namespace std;

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

int cntSplits(string s)

{

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

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

        return -1;

  

    // Для сохранения финального ответа

    int ans = 0;

  

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

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

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

  

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

    return ans;

}

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

int main()

{

    string s = "10010";

  

    cout << cntSplits(s);

  

    return 0;

}

Джава

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

class GFG

{

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

static int cntSplits(String s)

{

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

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

        return -1;

  

    // Для сохранения финального ответа

    int ans = 0;

  

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

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

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

  

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

    return ans;

}

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

public static void main(String []args) 

{

    String s = "10010";

  

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

}
}

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

python3

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

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

def cntSplits(s) :

  

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

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

        return -1

  

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

    ans = 0

  

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

    for i in range(len(s)) :

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

  

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

    return ans ; 

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

if __name__ == "__main__"

  

    s = "10010"

  

    print(cntSplits(s));

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

C #

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

using System;

                      

class GFG

{

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

static int cntSplits(String s)

{

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

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

        return -1;

  

    // Для сохранения финального ответа

    int ans = 0;

  

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

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

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

  

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

    return ans;

}

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

public static void Main(String []args) 

{

    String s = "10010";

  

    Console.WriteLine(cntSplits(s));

}
}

  
// Этот код предоставлен Rajput-Ji

Выход:

3

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

Максимальное количество разбиений двоичного числа

0.00 (0%) 0 votes