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

31.12.2019Массивы, Математика

Для данного массива из 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 i^th
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