Наименьшее число, которое не может быть образовано из суммы чисел из массива

Рассмотрим все целые числа в интервале [2 ⁱ .. 2 ^{i + 1} - 1]. И предположим, что все целые числа меньше 2 ⁱ могут быть образованы из суммы чисел из данного массива. Также предположим, что мы уже знаем C, который представляет собой сумму всех чисел ниже 2 ⁱ. Если C> = 2 ^{i + 1} - 1, каждое число в этом интервале может быть представлено как сумма заданных чисел. В противном случае мы могли бы проверить, содержит ли interval [2 ⁱ .. C + 1] какое-либо число из заданного массива. А если такого числа нет, мы искали C + 1.

Вот набросок алгоритма:

1. Для каждого входного числа определите, к какому интервалу он принадлежит, и обновите соответствующую сумму: S[int_log(x)] += x.
2. Вычислить сумму префикса для массива S: foreach i: C[i] = C[i-1] + S[i].
3. Отфильтруйте массив C, чтобы оставить только записи со значениями ниже следующей степени 2.
4. Просканируйте входной массив еще раз и обратите внимание, какой из интервалов [2 ⁱ .. C + 1] содержит хотя бы одно входное число: i = int_log(x) - 1; B[i] |= (x <= C[i] + 1).
5. Найдите первый интервал, который не отфильтрован на шаге №3 и соответствующий элемент B[] не установлен на шаге №4.

Если не очевидно, почему мы можем применить шаг 3, вот доказательство. Выберите любое число от 2 ⁱ до C, затем последовательно вычтите из него все числа ниже 2 ⁱ в порядке убывания. В конце концов мы получаем либо какое-то число меньше последнего вычтенного числа, либо ноль. Если результат равен нулю, просто сложите все вычтенные числа, и мы получим представление выбранного числа. Если результат не равен нулю и меньше последнего вычтенного числа, этот результат также меньше 2 ⁱ, поэтому он «представимый», и ни одно из вычтенных чисел не используется для его представления. Когда мы складываем эти вычтенные числа обратно, мы получаем представление выбранного числа. Это также предполагает, что вместо фильтрации интервалов по одному мы могли бы пропустить сразу несколько интервалов, перейдя непосредственно к int_log C.

Сложность времени определяется функцией int_log(), которая представляет собой целочисленный логарифм или индекс самого высокого установленного бита в числе. Если наш набор инструкций содержит целочисленный логарифм или любой его эквивалент (подсчет ведущих нулей или трюки с числами с плавающей запятой), то сложность равна O (n). В противном случае мы могли бы использовать некоторый битовый взлом, чтобы реализовать int_log() в O (log log U) и получить временную сложность O (n * log log U). (Здесь U - наибольшее число в массиве).

Если шаг 1 (помимо обновления суммы) также обновит минимальное значение в заданном диапазоне, шаг 4 больше не нужен. Мы могли бы просто сравнить C [i] с Min [i + 1]. Это означает, что нам нужен только один проход по входному массиву. Или мы могли бы применить этот алгоритм не к массиву, а к потоку чисел.

Несколько примеров:

Input:       [ 4 13  2  3  1]    [ 1  2  3  9]    [ 1  1  2  9]
int_log:       2  3  1  1  0       0  1  1  3       0  0  1  3

int_log:     0  1  2  3          0  1  2  3       0  1  2  3
S:           1  5  4 13          1  5  0  9       2  2  0  9
C:           1  6 10 23          1  6  6 15       2  4  4 13
filtered(C): n  n  n  n          n  n  n  n       n  n  n  n
number in
[2^i..C+1]:  2  4  -             2  -  -          2  -  -
C+1:              11                7                5

Для входных чисел с разной точностью этот подход требует времени O (n * log M) и пространства O (log M). Где M - наибольшее число в массиве. То же время нужно просто для чтения всех чисел (а в худшем случае нам понадобится каждый их бит).

Тем не менее, этот результат может быть улучшен до O (n * log R), где R - значение, найденное этим алгоритмом (фактически, его вариант, чувствительный к выходу). Единственная модификация, необходимая для этой оптимизации, состоит в том, чтобы вместо обработки целых чисел сразу обрабатывать их по цифрам: первый проход обрабатывает младшие биты каждого числа (например, биты 0..63), второй проход - следующие биты (например, 64..127) и т. Д. Мы можем игнорировать все старшие биты после нахождения результата. Также это уменьшает требования к пространству до O (K) чисел, где K - количество битов в машинном слове.

Есть красивый алгоритм для решения этой проблемы за время O (n + Sort), где Sort - это количество времени, необходимое для сортировки входного массива.

Идея алгоритма состоит в том, чтобы отсортировать массив, а затем задать следующий вопрос: какое наименьшее положительное целое число вы не можете получить, используя первые k элементов массива? Затем вы просматриваете массив слева направо, обновляя свой ответ на этот вопрос, пока не найдете наименьшее число, которое вы не можете составить.

Вот как это работает. Изначально наименьшее число, которое вы не можете составить, - 1. Затем, двигаясь слева направо, выполните следующие действия:

• Если текущее число больше наименьшего числа, которое вы не можете составить до сих пор, тогда вы знаете наименьшее число, которое вы не можете составить - это то, которое вы записали, и все готово.
• В противном случае текущее число меньше или равно наименьшему числу, которое вы не можете составить. Утверждают, что вы действительно можете сделать это число. Прямо сейчас вы знаете наименьшее число, которое вы не можете составить с первыми k элементами массива (назовите его candidate), и теперь смотрите на значение A[k]. Следовательно, число candidate - A[k] должно быть некоторым числом, которое вы действительно можете составить с первыми k элементами массива, поскольку в противном случае candidate - A[k] было бы меньшим числом, чем наименьшее число, которое вы якобы не можете составить с первыми k числами в массиве. Более того, вы можете создать любое число в диапазоне от candidate до candidate + A[k] включительно, потому что вы можете начать с любого числа в диапазоне от 1 до A[k] включительно, а затем добавить к нему candidate - 1. Поэтому установите candidate на candidate + A[k] и увеличьте k.

В псевдокоде:

Sort(A)
candidate = 1
for i from 1 to length(A):
   if A[i] > candidate: return candidate
   else: candidate = candidate + A[i]
return candidate

Вот тестовый прогон на [4, 13, 2, 1, 3]. Отсортируйте массив, чтобы получить [1, 2, 3, 4, 13]. Затем установите candidate в 1. Затем мы делаем следующее:

• A[1] = 1, candidate = 1:
  • A[1] ≤ candidate, so set candidate = candidate + A[1] = 2
• A[2] = 2, candidate = 2:
  • A[2] ≤ candidate, so set candidate = candidate + A[2] = 4
• A[3] = 3, candidate = 4:
  • A[3] ≤ candidate, so set candidate = candidate + A[3] = 7
• A[4] = 4, candidate = 7:
  • A[4] ≤ candidate, so set candidate = candidate + A[4] = 11
• A[5] = 13, candidate = 11:
  • A[4] > candidate, so return candidate (11).

Итак, ответ - 11.

Время выполнения здесь - O (n + Sort), потому что вне сортировки время выполнения - O (n). Вы можете четко отсортировать по времени O (n log n) с помощью heapsort, и если вы знаете некоторую верхнюю границу чисел, вы можете отсортировать по времени O (n log U) (где U - максимально возможное число) с помощью сортировки по основанию. Если U - фиксированная константа (скажем, 10 ⁹), то радиальная сортировка выполняется за время O (n), и весь этот алгоритм затем также выполняется за время O (n).

Надеюсь это поможет!

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

Начните с пустого битового вектора b. Затем для каждого элемента k в вашем массиве сделайте следующее:

b = b | b << k | 2^(k-1)

Для ясности, i-й элемент установлен в 1, чтобы представить число i, а | k устанавливает k-й элемент в 1.

После того, как вы закончите обработку массива, вашим ответом будет индекс первого нуля в b (считая справа, начиная с 1).

1. b=0
2. процесс 4: b = b | b ‹---------------- 4 | 1000 = 1000
3. процесс 13: b = b | b ‹закрыть 13 | 1000000000000 = 10001000000001000
4. процесс 2: b = b | b ‹---------------- 2 | 10 = 1010101000000101010
5. процесс 3: b = b | b ‹---------------- 3 | 100 = 1011111101000101111110
6. процесс 1: b = b | b ‹---------------- 1 | 1 = 11111111111001111111111

Первый ноль: позиция 11.

Если вы отсортируете массив, он подойдет вам. Подсчетная сортировка могла бы сделать это за O(n), но если вы думаете о практически большом сценарии, диапазон может быть довольно большим.

Quicksort O(n*logn) сделает всю работу за вас:

def smallestPositiveInteger(self, array): 
    candidate = 1
    n = len(array)
    array = sorted(array)
    for i in range(0, n):
        if array[i] <= candidate:
            candidate += array[i]
        else:
            break
    return candidate