Реализация на Python

На эту проблему отвечает Geeksforgeeks (здесь) и еще одна статья на Medium (здесь). Однако первое слишком короткое (осталось много деталей), а второе слишком длинное (включено слишком много деталей). Моя задача здесь состоит в том, чтобы сделать объяснение как можно более лаконичным, но при этом более познавательным.

Перейдем к проблеме.

Глупое решение: грубая сила

Это занимает экспоненциальное время и, вероятно, никогда не вернет результат для больших массивов. Кроме того, ни один интервьюер не принимает такой ответ; Итак, давайте представим, что этого решения не существует.

Лучшее решение:

В этом вопросе есть два ключевых факта, которые позволяют нам решить его за O(n) время.

  1. Массив отсортирован. В противном случае вы не сможете решить ее менее чем за O(n*log(n)) раз.
  2. Начиная с начала массива, первое значение больше (сумма всех предыдущих значений + 1) - это то место, где у нас будет пробел. Окончательный ответ (сумма всех предыдущих значений + 1).

Но вы можете задаться вопросом, в чем магия первого значения в массиве больше (сумма всех предыдущих значений + 1)? Почему значения, меньшие или равные (сумма всех предыдущих значений + 1), являются допустимыми, и мы проходим мимо этих значений?

В порядке. В приведенном выше алгоритме result-1 - это в основном значение максимально возможного целого числа, которое может быть представлено. Другими словами, могут быть представлены все положительные целые числа от 1 до result-1, т. Е. 1, 2, 3, …, result -1

Для каждого значения массива, если значение меньше или равно result, тогда могут быть представлены все положительные целые числа от 1 до result - 1 + array value, а result + array value будет наименьшим значением, которое не может быть представлено.

Но если значение массива больше, чем result, тогда будет по крайней мере одно положительное целое число от 1 до result + array value, которое не может быть представлено.

Давайте объясним все эти шаги на примере, предполагая, что arr = [1, 1, 2, 4,6]. Ниже представлена ​​пошаговая иллюстрация алгоритма.

Для индекса 3 значение массива равно 4, что меньше result = 5. Итак, result переходит на result + 4 = 9. Почему? потому что когда result = 5, это означает, что мы можем представлять значения 1, 2, 3, and 4. Добавление 4 в сгиб позволяет нам представить 1+4, 2+4, 3+4, and 4+4. Как видите, максимально возможное значение становится 8, и поэтому наименьшее значение, которое не может быть представлено, то есть result, становится 9.

Для индекса 4 значение массива - 11, что больше, чем result = 9. По тому же аргументу, если мы продолжим и включим 9, мы можем представить 12, 13, 14, …, 19. Как вы ясно видите, у нас есть пробел для целых чисел 10 и 11, и он не принимается. Вот почему мы должны разорвать цикл и произнести result = 9 как наименьшее значение, которое не может быть представлено как сумма любого подмножества данного массива.

Реализация на Python:

def findSmallest(arr, n): 
  
    result = 1
  
    for i in range (0, n ): 
        if arr[i] <= result: 
            result = result + arr[i] 
        else: 
            break
    return result
# Driver Code
if __name__ == "__main__":
    
    arr = [1, 1, 2, 4, 11] 
    n = len(arr) 
    print(findSmallest(arr, n))

Если вы нашли эту статью полезной, поделитесь ею со своими друзьями и коллегами. Если у вас есть другие вопросы, вы можете найти меня в Linkedin или написать мне на почту [email protected].