UniLecs #Task. Impossible amount

Published in

UniLecs

1 min readDec 9, 2019

Задача: дан массив натуральных чисел. Необходимо определить минимальное натуральное число, которое не образуется суммой никаких из этих чисел.

Примечание: в сумму каждое исходное число может входить не более одного раза.

Входные данные: arr — массив натуральных чисел, размер массива от 1 до 10⁴.

Вывод: искомое минимальное натуральное число.

Пример:

1. arr = [1, 1, 1, 5];

Output: 4.

2. arr = [1, 2, 4, 8];

Output: 16

Разбор

Отсортируем исходный массив. Далее пусть Sk = Sum(arr)(от 1го до k-го).

Если (Sk + 1) < arr[k + 1], то число (Sk + 1) не представимо в виде суммы элементов массива arr.
Если для всех k выполняется неравенство (Sk + 1) < arr[k + 1], то искомым числом будет (Sn + 1), где n — размер массива arr.