Рубрики

Минимальное количество переключений для разбиения двоичного массива, чтобы он имел сначала 0, а затем 1 с.

Для данного массива из n целых чисел, содержащего только 0 и 1. Найдите минимальные переключатели (переключение с 0 на 1 или наоборот), необходимые для массива, в котором массив становится секционированным, т. Е. Он имеет сначала 0, а затем 1. В начале должен быть хотя бы один 0, а в конце может быть ноль или более 1.

Input: arr[] = {1, 0, 1, 1, 0}
Output: 2
Toggle the first and last element i.e.,
1 -> 0
0 -> 1
Final array will become:
arr[] = {0 0 1 1 1}
Since first two consecutive elements are all 0s
and rest three consecutive elements are all 1s.
Therefore minimum two toggles are required.

Input: arr[] = {0, 1, 0, 0, 1, 1, 1}
Output: 1

Input: arr[] = {1, 1}
Output: 1
There should be at least one 0.

Input: arr[] = {0, 0}
Output: 0
There can zero 1s.

Если мы посмотрим на вопрос, то обнаружим, что определенно будет существовать точка от 0 до n-1, где все элементы, оставленные до этой точки, должны содержать все 0, а справа от точки должны содержать все 1. Те индексы, которые не подчиняются этому закону, должны быть удалены. Идея состоит в том, чтобы считать все 0 слева направо.

Let zero[i] denotes the number of 0's till ith
index, then for each i, minimum number of
toggles required can be written as: i - zero[i]
 + zero[n] - zero[i] . The part i - zero[i]
indicates number of 1's to be toggled and the 
part zero[n] - zero[i] indicates number of 0's
to be toggled.

After that we just need to take minimum of 
all to get the final answer.

C ++

// C ++ программа, чтобы найти минимальное необходимое переключение
#include <bits/stdc++.h>

using namespace std;

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

int minToggle(int arr[], int n)

{

    int zero[n + 1];

    zero[0] = 0;

  

    // Заполняем записи нулями [] так, чтобы ноль [i]

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

    // (exl

    for (int i = 1; i <= n; ++i) {

        // Если найден ноль, обновить ноль [] массив

        if (arr[i - 1] == 0)

            zero[i] = zero[i - 1] + 1;

        else

            zero[i] = zero[i - 1];

    }

  

    // Находим минимальное необходимое переключение из

    // каждый индекс (от 0 до n-1)

    int ans = n;

    for (int i = 1; i <= n; ++i)

        ans = min(ans, i - zero[i] + zero[n] - zero[i]);

  

    return ans;

}

  
// Программа для водителя

int main()

{

    int arr[] = { 1, 0, 1, 1, 0 };

    int n = sizeof(arr) / sizeof(arr[0]);

    cout << minToggle(arr, n) << "\n";

    return 0;

}

Джава

// Java программа для поиска минимума
// требуется переключение

import java.io.*;

  

class GFG {

  

    // Функция для расчета минимального переключения

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

    static int minToggle(int arr[], int n)

    {

        int zero[] = new int[n + 1];

        zero[0] = 0;

  

        // Заполняем записи нулями [] так, чтобы

        // zero [i] сохраняет количество нулей

        // слева от меня (exl

        for (int i = 1; i <= n; ++i) {

            // Если найден ноль, обновить ноль [] массив

            if (arr[i - 1] == 0)

                zero[i] = zero[i - 1] + 1;

            else

                zero[i] = zero[i - 1];

        }

  

        // Находим минимальное необходимое переключение

        // из каждого индекса (от 0 до n-1)

        int ans = n;

        for (int i = 1; i <= n; ++i)

            ans = Math.min(ans, i - zero[i] + zero[n]

                                    - zero[i]);

  

        return ans;

    }

  

    // Программа для водителя

    public static void main(String[] args)

    {

        int arr[] = { 1, 0, 1, 1, 0 };

        int n = arr.length;

        System.out.println(minToggle(arr, n));

    }

}

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

python3

# Python программа для поиска
# минимальное необходимое переключение

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

def minToggle(arr, n):

  

    zero =[0 for i in range(n + 1+1)]

    zero[0] = 0

   

    # Заполните записи в ноль []

    # такой, что ноль [я]

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

    # слева от меня

    # (exl

    for i in range(1, n + 1):

      

        # Если найден ноль

        # update zero [] массив

        if (arr[i-1] == 0):

            zero[i] = zero[i-1] + 1

        else:

            zero[i] = zero[i-1]

   

    # Нахождение минимума

    # требуется переключение с

    # каждый индекс (от 0 до n-1)

    ans = n

    for i in range(1, n + 1):

        ans = min(ans, i - zero[i] + zero[n] - zero[i])

   

    return ans

      
# Драйверная программа

  

arr = [1, 0, 1, 1, 0]

n = len(arr)

  

print(minToggle(arr, n))

  
# Этот код добавлен
# Анант Агарвал.

C #

// C # программа для поиска минимума
// требуется переключение

using System;

  

class GFG {

  

    // Функция для расчета минимального переключения

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

    static int minToggle(int[] arr, int n)

    {

          

        int[] zero = new int[n + 1];

        zero[0] = 0;

  

        // Заполняем записи нулями [] так, чтобы

        // zero [i] сохраняет количество нулей

        // слева от меня (exl

        for (int i = 1; i <= n; ++i) {

              

            // Если ноль найден, обновить ноль []

            // массив

            if (arr[i - 1] == 0)

                zero[i] = zero[i - 1] + 1;

            else

                zero[i] = zero[i - 1];

        }

  

        // Находим минимальное необходимое переключение

        // из каждого индекса (от 0 до n-1)

        int ans = n;

          

        for (int i = 1; i <= n; ++i)

            ans = Math.Min(ans, i - zero[i] +

                            zero[n] - zero[i]);

  

        return ans;

    }

  

    // Программа для водителя

    public static void Main()

    {

        int[] arr = { 1, 0, 1, 1, 0 };

        int n = arr.Length;

          

        Console.WriteLine(minToggle(arr, n));

    }

}

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

PHP

<?php
// программа php, чтобы найти минимальное необходимое переключение

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

function minToggle($arr, $n)

{

    $zero[0] = 0;

    $zero[$n + 1]=0;

  

  

    // Заполняем записи нулями [] так, чтобы ноль [i]

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

    // (exl

    for ($i = 1; $i <= $n; ++$i) {

          

        // Если найден ноль, обновить ноль [] массив

        if ($arr[$i - 1] == 0)

            $zero[$i] = $zero[$i - 1] + 1;

        else

            $zero[$i] = $zero[$i - 1];

    }

  

    // Находим минимальное необходимое переключение из

    // каждый индекс (от 0 до n-1)

    $ans = $n;

      

    for ($i = 1; $i <= $n; ++$i)

        $ans = min($ans, $i - $zero[$i]

                      + $zero[$n] - $zero[$i]);

  

    return $ans;

}

  
// Программа для водителя

    $arr = array( 1, 0, 1, 1, 0 );

    $n = sizeof($arr);

      

    echo minToggle($arr, $n) , "\n";

  
// Этот код предоставлен нитин митталь.
?>


Выход:

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

Минимальное количество переключений для разбиения двоичного массива, чтобы он имел сначала 0, а затем 1 с.

0.00 (0%) 0 votes