Как найти количество нулей в массиве - Исправление недочетов и поиск решений вместе с Examum.ru

Improve Article

Save Article

Like Article

Read

Discuss(50+)

Improve Article

Save Article

Like Article

Given an array of 1s and 0s which has all 1s first followed by all 0s. Find the number of 0s. Count the number of zeroes in the given array.
Examples :

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

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

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

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

Approach 1: A simple solution is to traverse the input array. As soon as we find a 0, we return n – index of first 0. Here n is number of elements in input array. Time complexity of this solution would be O(n).

Implementation of above approach is below:

C++

#include <bits/stdc++.h>

using namespace std;

int firstzeroindex(int arr[], int n)

{

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

if (arr[i] == 0) {

return i;

}

return -1;

}

int main()

{

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

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

int x = firstzeroindex(arr, n);

if (x == -1) {

cout << "Count of zero is 0" << endl;

}

else {

cout << "count of zero is " << n - x << endl;

}

return 0;

}

Java

import java.io.*;

class GFG {

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

{

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

if (arr[i] == 0) {

return i;

}

return -1;

}

public static void main(String[] args)

{

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

int n = arr.length;

int x = firstzeroindex(arr, n);

if (x == -1) {

System.out.println("Count of zero is 0");

}

else {

System.out.print("count of zero is ");

System.out.println(n-x);

}

Python3

class GFG :

@staticmethod

def firstzeroindex( arr, n) :

i = 0

while (i < n) :

if (arr[i] == 0) :

return i

i += 1

return -1

@staticmethod

def main( args) :

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

n = len(arr)

x = GFG.firstzeroindex(arr, n)

if (x == -1) :

print("Count of zero is 0")

else :

print("count of zero is ", end ="")

print(n - x)

if __name__=="__main__":

GFG.main([])

C#

using System;

public class GFG{

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

{

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

if (arr[i] == 0) {

return i;

}

return -1;

}

public static void Main()

{

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

int n = arr.Length;

int x = firstzeroindex(arr, n);

if (x == -1) {

Console.WriteLine("Count of zero is 0");

}

else {

Console.Write("count of zero is ");

Console.WriteLine(n-x);

}

Javascript

<script>

function firstzeroindex(arr, n)

{

for (let i = 0; i < n; i++) {

if (arr[i] == 0) {

return i;

}

return -1;

}

let arr = [ 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0 ];

let n = arr.length;

let x = firstzeroindex(arr, n);

if (x == -1) {

document.write("Count of zero is 0");

}

else {

document.write("count of zero is " + (n-x));

}

</script>

Time complexity: O(n) where n is size of arr.

Space Complexity: O(1) as we are not using any extra space.

Approach 2: Since the input array is sorted, we can use Binary Search to find the first occurrence of 0. Once we have index of first element, we can return count as n – index of first zero.

Implementation:

C

#include <stdio.h>

int firstZero(int arr[], int low, int high)

{

if (high >= low)

{

int mid = low + (high - low)/2;

if (( mid == 0 || arr[mid-1] == 1) && arr[mid] == 0)

return mid;

if (arr[mid] == 1)

return firstZero(arr, (mid + 1), high);

else

return firstZero(arr, low, (mid -1));

}

return -1;

}

int countZeroes(int arr[], int n)

{

int first = firstZero(arr, 0, n-1);

if (first == -1)

return 0;

return (n - first);

}

int main()

{

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

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

printf("Count of zeroes is %d", countZeroes(arr, n));

return 0;

}

C++

#include <bits/stdc++.h>

using namespace std;

int firstZero(int arr[], int low, int high)

{

if (high >= low)

{

int mid = low + (high - low) / 2;

if ((mid == 0 || arr[mid - 1] == 1) &&

arr[mid] == 0)

return mid;

if (arr[mid] == 1)

return firstZero(arr, (mid + 1), high);

else

return firstZero(arr, low, (mid -1));

}

return -1;

}

int countZeroes(int arr[], int n)

{

int first = firstZero(arr, 0, n - 1);

if (first == -1)

return 0;

return (n - first);

}

int main()

{

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

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

cout << "Count of zeroes is "

<< countZeroes(arr, n);

return 0;

}

Java

class CountZeros

{

int firstZero(int arr[], int low, int high)

{

if (high >= low)

{

int mid = low + (high - low) / 2;

if ((mid == 0 || arr[mid - 1] == 1) && arr[mid] == 0)

return mid;

if (arr[mid] == 1)

return firstZero(arr, (mid + 1), high);

else

return firstZero(arr, low, (mid - 1));

}

return -1;

}

int countZeroes(int arr[], int n)

{

int first = firstZero(arr, 0, n - 1);

if (first == -1)

return 0;

return (n - first);

}

public static void main(String[] args)

{

CountZeros count = new CountZeros();

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

int n = arr.length;

System.out.println("Count of zeroes is " + count.countZeroes(arr, n));

}

Python3

def firstZero(arr, low, high):

if (high >= low):

mid = low + int((high - low) / 2)

if (( mid == 0 or arr[mid-1] == 1)

and arr[mid] == 0):

return mid

if (arr[mid] == 1):

return firstZero(arr, (mid + 1), high)

else:

return firstZero(arr, low, (mid - 1))

return -1

def countZeroes(arr, n):

first = firstZero(arr, 0, n - 1)

if (first == -1):

return 0

return (n - first)

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

n = len(arr)

print("Count of zeroes is",

countZeroes(arr, n))

C#

using System;

class CountZeros

{

int firstZero(int []arr, int low, int high)

{

if (high >= low)

{

int mid = low + (high - low) / 2;

if ((mid == 0 || arr[mid - 1] == 1) &&

arr[mid] == 0)

return mid;

if (arr[mid] == 1)

return firstZero(arr, (mid + 1), high);

else

return firstZero(arr, low, (mid - 1));

}

return -1;

}

int countZeroes(int []arr, int n)

{

int first = firstZero(arr, 0, n - 1);

if (first == -1)

return 0;

return (n - first);

}

public static void Main()

{

CountZeros count = new CountZeros();

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

int n = arr.Length;

Console.Write("Count of zeroes is " +

count.countZeroes(arr, n));

}

PHP

<?php

function firstZero($arr, $low, $high)

{

if ($high >= $low)

{

$mid = $low + floor(($high - $low)/2);

if (( $mid == 0 || $arr[$mid-1] == 1) &&

$arr[$mid] == 0)

return $mid;

if ($arr[$mid] == 1)

return firstZero($arr, ($mid + 1), $high);

else

return firstZero($arr, $low,

($mid - 1));

}

return -1;

}

function countZeroes($arr, $n)

{

$first = firstZero($arr, 0, $n - 1);

if ($first == -1)

return 0;

return ($n - $first);

}

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

$n = sizeof($arr);

echo("Count of zeroes is ");

echo(countZeroes($arr, $n));

?>

Javascript

<script>

function firstZero(arr , low , high) {

if (high >= low) {

var mid = low + parseInt((high - low) / 2);

if ((mid == 0 || arr[mid - 1] == 1) && arr[mid] == 0)

return mid;

if (arr[mid] == 1)

return firstZero(arr, (mid + 1), high);

else

return firstZero(arr, low, (mid - 1));

}

return -1;

}

function countZeroes(arr , n)

{

var first = firstZero(arr, 0, n - 1);

if (first == -1)

return 0;

return (n - first);

}

var arr = [ 1, 1, 1, 0, 0, 0, 0, 0 ];

var n = arr.length;

document.write("Count of zeroes is " + countZeroes(arr, n));

</script>

Output

Count of zeroes is 5

Time Complexity: O(Logn) where n is number of elements in arr[].

Auxiliary Space: O(logn)

Last Updated :
20 Feb, 2023

Like Article

Save Article

Источник

Раздел:
Задачи /
Простейшие /

Найти количество нулей во всех числах последовательности

Основы программирования
Каждый профессионал когда-то был чайником. Наверняка вам знакомо состояние, когда “не знаешь как начать думать, чтобы до такого додуматься”. Наверняка вы сталкивались с ситуацией, когда вы просто не знаете, с чего начать.
Эта книга ориентирована как раз на таких людей, кто хотел бы стать программистом, но совершенно не знает, как начать этот путь.
Подробнее…

Условие задачи 0.4

Задача 0.4
Дана последовательность чисел, заданная пользователем. Найти количество нулей во всех числах последовательности.

В этот раз решил немного отойти от традиций и решить задачу на нескольких языках.
А именно: 1) Паскаль;
2) С++;
3) JavaScript; 4) VBScript; 5) VBA.

А сподвигла меня на это просьба одного из читателей, который и попросил помочь в решении этой задачи. Правда, просил он только о VBA, но я решил расширить эту просьбу. И хотя к тому времени, когда я собрался это сделать, для читателя задача уже была неактуальна, я решил таки её решить — вдруг кому-то ещё пригодится…

ПРИМЕЧАНИЕ
Скачать исходные коды всех примеров можно здесь.

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

В заголовке, в общем то, отражена суть решения задачи. Нам надо просто подсчитать количество нулей в строке, которую ввёл пользователь.

В большинстве языков программирования с вводом строки не будет никаких сложностей (хотя есть особенности — о вводе данных более подробно расскажу ниже).

Для решения лучше всего создать функцию, которая будет принимать строку, а возвращать количество нулей в этой строке. Далее привожу примеры такой функции на нескольких языках.

Пример на Паскале

//-------------------------------------------------------------------
// Вычисляет и возвращает количество нулей в строке st
//-------------------------------------------------------------------
function GetZerosNum(st : string) : word;
var i, n : word;
begin
  n := 0;
  for i := 1 to Length(st) do
    if st[i] = '0' then Inc(n);
  Result := n;
end;

Пример на С++

unsigned int GetZerosNum(string st) 
{
  unsigned int i, n = 0;	  
  for (i = 0; i < st.length(); i++)
    if (st[i] == '0') n++;  
  return n;
}

Пример на JavaScript

function GetZerosNum(st)
{ 
  var i, n = 0;	  
  for (i = 0; i < st.length; i++)
    if (st.charAt(i) == '0') n++;
  return n;
}

Пример на VBScript и VBA

'--------------------------------------------------------------------
' Вычисляет и возвращает количество нулей в строке st
'--------------------------------------------------------------------
function GetZerosNum(st) 
  n = 0
  for i = 1 to Len(st) 
    if Mid(st, i, 1) = "0" then n = n + 1
    next
  GetZerosNum = n
end function

Ну вот как-то так. Теперь ещё осталось разобраться с вводом данных.
Для всех случаев я решил использовать глобальную переменную str, в которую буду получать строку, введённую пользователем.

В Паскале никаких сложностей с этим нет — просто используйте

ReadLn(str);

Снова и снова убеждаюсь, что Паскаль — это очень крутой и простой язык.
А вот в С++ всё будет не так просто. Если вы используете cin, то будете неприятно удивлены тем обстоятельством, что строка будет прочитана только до первого пробела. Поэтому придётся сделать так:

getline(cin, str);

В JavaScript я использовал поле ввода. Как это делается, я рассказал
здесь.

В VBScript я использовал диалоговое окно для ввода данных. Подробно об этом
я рассказал в книге Как стать программистом.

VBA — это язык, о котором я раньше вообще не рассказывал. Не буду
рассказывать и сейчас, потому что это тема отдельного разговора.
Скажу только, что для примера я использовал файл Excel,
в котором размести кнопку и связал её с макросом, который и вызывает функцию GetZerosNum.

Пользователь вводит данные в ячейку таблицы Excel, а макрос на языке VBA читает данные из этой ячейки и подсчитывает количество нулей. Итог расчета выводится в другую ячейку.

Что из всего этого получилось, см. на рисунках.

Ну вот и всё. Надеюсь, вам было любопытно понаблюдать как творят программисты на разных языках. И, как видите, дело не в языке — дело в том, что именно для вашей задачи более удобно. И пусть этот простой пример не так ярко показывает возможности разных языков, но он однозначно показывает, что все языки по своему хороши…

ВНИМАНИЕ!
Если вам что-то осталось непонятно в примерах на Паскале, С++ и JavaScript, то советую почитать книги
“Основы программирования”,
“Основы С++” и
“Что такое JavaScript”.

Как стать программистом 2.0

Эта книга для тех, кто хочет стать программистом. На самом деле хочет, а не просто мечтает. И хочет именно стать программистом с большой буквы, а не просто научиться кулебякать какие-то примитивные программки…
Подробнее…

Помощь в технических вопросах

Помощь студентам. Курсовые, дипломы, чертежи (КОМПАС), задачи по программированию: Pascal/Delphi/Lazarus; С/С++; Ассемблер; языки программирования ПЛК; JavaScript; VBScript; Fortran; Python и др. Разработка (доработка) ПО ПЛК (предпочтение — ОВЕН, CoDeSys 2 и 3), а также программирование панелей оператора, программируемых реле и других приборов систем автоматизации.
Подробнее…

Источник

Sabach
Подсказку не дадите для дилетанта?

Sabach
но в задании стоит не использовать функции

input и print — это функции.

  
>>> input
<built-in function input>
>>> print
<built-in function print>
>>>

Видимо, тебе запрещено использовать

методы

списка, кортежа и других аналогов массива.

Sabach
Как объединить оба кода, чтобы и введенный массив показывал и нули подсчитывал (желательно через if)?

Во-первых, ты ошибочно думаешь, что их надо объединять. В программировании нужно, наоборот, всё разделять при первой же возможности. Модульная система. Если в одном модуле что-то произошло, то надо его просто изолировать, чтобы вся программа продолжила работать или разрабатываться в прежнем режиме. Это как на подводной лодке или на космической станции — при любом ЧП изолируется отсек (он же модуль).
Поэтому сначала ты должен ввести данные,

и только после этого

ты должен работать с данными.

Тут пошёл алгоритм:
1. Ввести данные.
2. Посчитать нули.
3. Вывести результаты.

Каждое действие выполняешь по очереди и следующее действие не начинаешь, пока полностью не закончишь предыдущее.

Сам всё сделаешь? Начни с первого действия и полностью его выполни. Покажи код, чтобы тебе сказали “да, правильно сделал это”. После этого сделай второе действие и полностью его выполни. Покажи код, чтобы тебе сказали “да, правильно сделал это”. Либо тебе скажут на втором действии “нет, неправильно ты это сделал”. Тогда ты станешь переделывать второе действие, но при этом первое действие не будет затронуто этой корректировкой, так как оно выполнено правильно. Это метод отсечений: написал что-то правильно — отложил в сторону, приступил к следующему. Когда у тебя первое действие выполнено правильно, второе действие выполнено правильно, только тогда ты делаешь третье действие. И так же приходишь и показываешь код и тебе говорят “да, правильно сделал это”. Когда у тебя первое действие выполнено правильно, второе действие выполнено правильно, третье действие выполнено правильно, тогда ты правильно выполнил

весь алгоритм

. Тут кроется маленький секрет: этот весь алгоритм потом становится одним маленьким действием в другом алгоритме, а тот другой алгоритм сам по себе тоже потом становится одним маленьким действием в ещё каком-то другом алгоритме. И тут кроется ещё один секрет: если тебе надо посчитать нули на сайте, а не в массиве, то ты берёшь готовый алгоритм и заменяешь полностью в нём первое действие, не затрагивая ничего во втором действии и в третьем действии. Это называется переиспользованием (reuse или по-русски реюз) кода — когда вместо написания кода с нуля ты берёшь откуда-то уже написанный ранее код (из другого проекта, из другого решения другой задачи, из кода другого автора другого проекта и тому подобного).

Как только ты начнёшь соблюдать эти элементарные правила и строго следовать им, сразу начнёт всё получаться и с вводом, и с циклами, и с красивым выводом. Всё это связано с тем, что хорошие алгоритмы вставляются в хорошие алгоритмы. Но хорошие алгоритмы пишутся по строгим правилам.

tags: algorithm module reuse

Отредактировано py.user.next (Июль 4, 2020 01:10:14)

Источник

Прошу помочь найти ошибку. Считает все элементы

private void button1_Click(object sender, EventArgs e)
    {

            var k = richTextBox1.Lines.Count(s => s == "0" || s == "1");
            string[] b = richTextBox1.Lines;
            int n = b.Length;
            int[] a = new int[n];
            int i;

            for (i = 0; i < n; i++)
            {
                a[i] = Convert.ToInt32(b[i]);                  
                if (a[i] == 0){
                {

                    textBox1.Text =Convert.ToString(k);

                }   }

                 if (a[i] == 1)
                {
                    {
                        textBox2.Text = Convert.ToString(k);

                    }
                }

            }

        }

задан 11 сен 2016 в 15:30

У тебя похоже ошибка в строчках:

textBox1.Text =Convert.ToString(k);

У тебя там , судя по коду, подсчитаны элемент, которые равны 0 и 1.

И ты каждый раз выводишь одно и тоже значение. Правильнее было завести какой-нибудь счетчик и инкреминитировать его при достижении условия.

Так же не ясен смысл цикла for, если ты через LINQ умеешь считать 0 и 1:

var k = richTextBox1.Lines.Count(s => s == "0" || s == "1");

Почему бы так же не сосчитать 0 и 1 отдельно?

ответ дан 11 сен 2016 в 15:39

iluxa1810iluxa1810

24.6k12 золотых знаков60 серебряных знаков151 бронзовый знак

Источник

Условие задачи: В заданном одномерном массиве, состоящем из n целых чисел, подсчитать количество нулей (Язык Pascal)

Сложность: легкая.

Решение задачи

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

Для того чтобы подсчитать количество нулей в одномерном массиве нам понадобиться следующие переменные :

Переменная mass — для массива

Переменная n — для количества элементов массива

Переменная count — для количества нулевых элементов

Переменная i — счетчик для цикла

Переменная number — для числа массива

Начнем мы с каркаса нашей программы

type

massiv =
array
[
1..100
]
of
integer
;
var

mass : massiv;

count , number , i , n :
integer
;
begin
randomize;
write
(
'Введите кол-во элементов : '
); readln(n);
end
.

Тут мы создали свой тип данных для массива, как и зачем читайте ( тут ) , дальше мы объявили все переменные которые у нас будут использоваться в программе и так как мы будем заполнять массив случайными числами, включили генератор случайных чисел, чтобы числа при каждом запуске программы были разные, подробнее ( тут ) , ну и попросили пользователя ввести кол-во элементов массива.

Ну а дальше довольно простой цикл :

for
i:=
1
to
n
do

begin

number := random(
6
);

write
(number,
' | '
);

if
( number =
0
)
then

count := count +
1
;

end
;

Цикл у нас само собой от 1 до кол-ва введенных пользователем чисел, в цикле мы присваиваем number, случайное число от 0 до 5, потом его выводим и проверяем с помощью условия равняется ли оно нулю, если да то увеличиваем кол-во нулевых чисел на один.

Ну и останется только вывести результат.

Всё решение задачи Pascal

uses
crt;
type

massiv =
array
[
1..100
]
of
integer
;
// создаем свой тип данных
var

mass : massiv;
// объявляем переменные

count , number , i , n :
integer
;
// объявляем переменные
begin
clrscr;
// очищаем экран
randomize;
// включаем генератор случайных чисел
write
(
'Введите кол-во элементов : '
); readln(n);
// вводим кол-во чисел
count :=
0
;
// обнуляем кол-во нулей чтобы не было ошибок
for
i:=
1
to
n
do
// пускаем цикл

begin

number := random(
6
);
// присваиваем случайное число

write
(number,
' | '
);
// выводим число

if
( number =
0
)
then
// если оно равно 0

count := count +
1
;
// увеличиваем кол-во нулей на 1

end
;
writeln
(
'Кол-во нулевых элементов : '
, count);
// выводим кол-во нулей
readln;
// чтобы программа не закрывалась.
end
.

ПрограммированиеЗадачи по Pascal. В одномерном массиве, состоящем из N вещественных элементов, вычислите количество элементов массива, меньших C

ПрограммированиеЗадачи по Pascal. Определите произведение первой и последней цифр в наименьшем натуральном числе, сумма цифр которого равна 2013

Источник