В массиве длины N содержатся все целые, различные числа от 0 до N, кроме одного. Составить алгоритм поиска пропущенного числа. Вводить дополнительные массивы не разрешается. Пример N, (4,2,5,0,1) Ответ: пропущенное число 3

14 Мар 2020 в 19:41
148 +1
0
Ответы
1

Для решения этой задачи можно воспользоваться формулой суммы арифметической прогрессии.
Сначала найдем сумму всех чисел от 0 до N по формуле: sum_N = N*(N+1)/2.
Затем пройдем по всем элементам массива и вычтем из суммы значение каждого элемента.
Пропущенное число будет равно разнице между sum_N и суммой всех элементов массива.

Пример реализации на Python:

def find_missing_number(arr):
n = len(arr)
sum_n = n*(n+1)//2
sum_arr = sum(arr)
missing_number = sum_n - sum_arr
return missing_number
arr = [4, 2, 5, 0, 1]
missing_number = find_missing_number(arr)
print("Пропущенное число:", missing_number)

Этот алгоритм работает за линейное время O(N), где N - длина массива.

18 Апр 2024 в 16:14
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Прямой эфир