Другие языки программирования и технологии

Вам даны все целые числа от 1 до N + 1, кроме одного. Найдите отсутствующее число.

В первой строке входных данных записано целое число 1 <= N <= 100,000. Во второй строке через пробел даны N целых чисел в диапазоне от 1 до N + 1.
т к число <2^17 то можно определить число по остатку от деления на 2^17
то есть достаточно получить последние 17 бит а если n< 65536 то и 16
то есть достаточно чтобы компилятор создавал код не проверяющий переполнение
Miras Kenzheev
Miras Kenzheev
4 234
Лучший ответ
Загнать исходный файл в список, отсортировать его, выполнить поиск тупым перебором.
Если числа по-порядку то:

for i:=1 to 100000 do
begin
read(file,x);
if x > i then
begin
writeln(i);
break;
end;
end;
Олег Сысоев спасибо вам!!!
Цикл от 1 до N+1, ищем по очереди каждое в полученном списке. То которое не находим - искомое.
MK
Marcel Kramer
78 634
Олег Сысоев Спасибо вам!!!
Если числа НЕ по-порядку, то предлагаю идею: числа от 1 до N + 1 - арифметическая прогрессия с шагом 1. Мы можем по простой формуле вычислить её сумму. Мы так же можем вычислить сумму всех чисел в файле (просто читаем по порядку и складываем). Так как в файле не хватает ОДНОГО числа, то сумма чисел в файле будем меньше суммы арифметической прогрессии ровно на это самое число (которое отсутствует в файле и которое нужно найти). Так как по условию задачи N <= 100000, максимальная сумма арифметической прогрессии составит 5 000 200 002. Это не помещается в 4 байта, поэтому используйте 8 байтовое целые числа.

read(N);
sum := 0;
S := (1 + (N + 1)) / 2 * (N + 1); {вычисляем сумму чисел от 1 до N + 1 включительно}
{читаем и складываем числа из файла}
for i:=1 to N do
begin
read(file,x);
sum := sum + x;
end;
{выводим искомое число как разность сумм}
writeln(S - sum);
Ххх Virt Для Девочек Кстати, можно сделать так: не вычислять сумму от 1 до N + 1 сразу, потому что можно неявно вычислить её в цикле во время чтения. Это затратит больше арифметических операций, зато не нужно париться с 64-битным целым числом

read(N);
sum := 0;

for i:=1 to N do
begin
read(file,x);
sum := sum + i - x;
end;

writeln(sum + N + 1);
Олег Сысоев Спасибо вам большое!!!

Похожие вопросы