🤯 Как простая задачка поставила в тупик программистов (и как они из него выбрались)

В 2010 году пользователь Stack Overflow не справился с задачей на собеседовании. Обсуждение способов решения этого задания стало одной из самых популярных тем на платформе.

Пользователю polygenelubricants задали на собеседовании такой вопрос: «В мешке находятся числа 1, 2, 3…100. Каждое число появляется только один раз, поэтому чисел ровно 100. Предположим, одно число вынули из мешка. Как определить это число?»

Это очень популярная задача, и разработчик без труда ее решил: «Сумму последовательности 1 + 2 + 3 + … + N можно определить по формуле (N+1)(N/2). Для N = 100 сумма будет равна 5050. Если вычесть из 5050 сумму чисел, которые остались в мешке, разница будет равна отсутствующему числу».

bag = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
       11, 12, 13, 14, 15, 16, 17, 18,
       19, 20, 21, 22, 23, 24, 25, 26,
       27, 28, 29, 30, 31, 32, 33, 34,
       35, 36, 37, 38, 39, 40, 41, 42,
       43, 44, 45, 46, 47, 48, 49, 50,
       51, 52, 53, 54, 55, 56, 57, 58,
       59, 60, 61, 62, 63, 64, 65, 66,
       67, 68, 69, 70, 71, 72, 73, 74,
       75, 76, 77, 78, 79, 80, 81, 82,
       83, 84, 86, 87, 88, 89, 90, 91,
       92, 93, 94, 95, 96, 97, 98, 99, 100] # отсутствует число 85
n = 100
missing_number = (n + 1) * (n / 2) - sum(bag)
print(int(missing_number)) # вывод = 85

Но радоваться было рано – коварный интервьюер задал следующий вопрос: «А как найти два отсутствующих числа»? Разработчик такого поворота событий не ожидал и запаниковал. Интервьюер пытался навести программиста на конструктивные размышления и намекнул, что есть подход для решения этой задачи, который:

  • Включает несколько уравнений.
  • Можно использовать для определения 2, 3, и даже k отсутствующих чисел.
  • Обладает лучшей временной и пространственной сложностью, чем О(n), потому что зависит от k.

Несколько месяцев разработчик размышлял над максимально оптимальным решением этой задачи для 2, 3, k ≥ 4 чисел, и наконец создал тему на Stack Overflow. К этому моменту легких решений он уже не искал:

  • Искомое решение должно работать не только для 100, но и для любого N чисел.
  • Не должно использовать самые очевидные подходы – битовый массив и сортировку.
  • Должно быть максимально универсальным, максимально эффективным, эдаким «Святым Граалем» всех возможных решений, даже если сложность реализации сделает этот подход непрактичным.

Два предложенных вариантa решения

Решений в теме много, но оптимальными являются только два. Одно из решений подходит для поиска пропущенных чисел в массиве или списке, второе можно использовать и для массива, и для потока данных.

Решение для массива

Этот элегантный алгоритм работает с линейной скоростью O(n) – чуть хуже, чем было нужно автору вопроса, – зато отличается универсальностью и полным отсутствием сложной математики:

import random
n = 11
k = 2

def find_k_missing(array, n):
    if len(array) == n:  
        return []
    if len(array) == 0:  
        return list(range(n))
    array.extend([array[0]] * (n - len(array)))
    for i in range(n):
        while array[i] != array[array[i]]:
            t = array[i]
            array[i] = array[t]
            array[t] = t
    return [i for i in range(n) if array[i] != i]

array = list(range(n))
random.shuffle(array)
array = array[:n-k]
print(f'Заданный массив: {array}')
result = find_k_missing(array, n)
print(f'Найденные числа: {result}')

Решение для потока данных

Этот подход взят из книги об алгоритмах для поточной обработки данных, автор которой ссылается на алгоритм Мински-Трахтенберга-Зиппеля, представленный в 2003 году. Метод очень эффективен – работает за O(k2 log n), и одинаково хорошо подходит как для массивов фиксированного размера, так и для потоков данных. Недостаток у него только один – относительная сложность реализации, которую предвидел автор вопроса.

Алгоритм построен на использовании симметричных многочленов, для вычисления которых нужно использовать тождества Ньютона и числа Бернулли. Из этих многочленов составляют систему уравнений или полином k-степени – корни будут равны пропущенным числам. Как именно это делается – рассмотрим ниже.

***

Как быстро освоить математику?

Заглядывай на наш онлайн-курс по математике для Data Science, где ты познакомишься с основными моделями машинного обучения, научишься выбирать и применять подходящие tree-based модели.

Программа занятий:

  • Школьная математика: от теории множеств до производной и интеграла.
  • Математический анализ: от числовых последовательностей до теории меры и интеграла Ламбера.
  • Линейная алгебра: от матриц до билинейных форм.
  • Комбинаторика: правила комбинаторики, множества и сочетания.
  • Теория вероятностей и математическая статистика: от случайных событий до регрессии.
  • Машинное обучение: Word2vec, градиентный спуск, KNN и т. д.
***

«Святой Грааль»

Пользователи, которым почему-то не понравилось «математическое» решение, предложенное в исходной теме, продолжили обсуждение в форке. Однако обсуждение быстро зашло в тупик, и это неудивительно: как показывает профессор Мэрилендского университета в Колледж-Парке Уильям Гасарш в этой публикации (pdf), на сегодняшний день известны только два относительно простых (и при этом очень эффективных) подхода для вычисления k ≥ 4, и оба используют симметрические функции. При использовании первого подхода симметрические многочлены выражаются через степенные суммы с помощью тождеств Ньютона, а при втором функции применяются на всех этапах решения.

Как найти 1, 2, 3 и k ≥ 4 пропущенных чисел в массиве или потоке

В упомянутой выше публикации Гасарш приводит 2-3 варианта решения для каждого случая. Все решения описаны математически. Так, например, выглядит первый вариант решения для общего случая:

Первое универсальное решение для любого k

А это второй вариант:

Второе универсальное решение для любого k

По представленным в публикации решениям несложно написать код. Рассмотрим несколько примеров.

Первый способ решения для k = 1:

def find_missing_number(nums):
    n = len(nums) + k
    expected_sum = n * (n + 1) / 2
    actual_sum = sum(nums)
    missing_number = (expected_sum - actual_sum) % n
    return missing_number

nums = [10, 1, 4, 7, 2, 3, 5, 9, 8]
k = 1
missing_number = find_missing_number(nums)
print(f"Пропущенное число: {missing_number:.0f}")

Второй способ решения для k = 1 (с использованием XOR):

def find_missing_number(nums):
    n = len(nums) + k
    xor_sum = 0
    for i in range(1, n + 1):
        xor_sum ^= i
    for num in nums:
        xor_sum ^= num
    return xor_sum

nums = [1, 10, 4, 7, 2, 3, 6, 9, 8]
k = 1
missing_number = find_missing_number(nums)
print(f"Пропущенное число: {missing_number}")

Решение для k = 2 с использование суммы квадратов:

def calculate_s_and_t(data):
    n = len(data) + k
    s_complete = n * (n + 1) / 2
    t_complete = n * (n + 1) * (2 * n + 1) / 6
    s_incomplete = sum(data)
    t_incomplete = sum(num**2 for num in data)
    s = s_complete - s_incomplete
    t = t_complete - t_incomplete
    return s, t

def find_roots(s, t):
    d = s**2 - 4 * ((s**2 - t) / 2)    
    if d >= 0:
        root1 = (-s + (d) ** 0.5) / 2
        root2 = (-s - (d) ** 0.5) / 2
        return root1, root2
    else:
        print("Уравнение имеет комплексные корни.")
        return None

data = [1, 2, 4, 6, 7, 8, 9, 10, 11, 12, 13]
k = 2
s, t = calculate_s_and_t(data)

roots = find_roots(s, t)
if roots:
    print(f"Найдены пропущенные числа: {roots[0] * -1:.0f} и {roots[1]* -1:.0f}")

Решение для k = 3 с использованием тождеств Ньютона

Основные шаги:

  • Вычисляем суммы степеней чисел от 1 до n, используя формулы суммирования степеней последовательных натуральных чисел. Это ожидаемые суммы степеней полного набора чисел.
  • Вычисляем неполные суммы степеней для фактически имеющихся чисел в списке data.
  • Находим разности между полными и неполными суммами степеней – это значения b1, b2, b3, которые представляют собой суммы соответствующих степеней недостающих чисел.
  • Используя тождества Ньютона, из найденных сумм степеней восстанавливаем коэффициенты c1, c2, c3 многочлена третьей степени, корнями которого являются недостающие числа.
import numpy as np

def calculate(data):
    n = len(data) + k
    а1_complete = n * (n + 1) / 2
    а2_complete = n * (n + 1) * (2 * n + 1) / 6
    а3_complete = n**2 * (n + 1)**2 / 4
    а1_incomplete = sum(data)
    а2_incomplete = sum(num**2 for num in data)
    а3_incomplete = sum(num**3 for num in data)
    b1 = а1_complete - а1_incomplete
    b2 = а2_complete - а2_incomplete
    b3 = а3_complete - а3_incomplete
    return b1, b2, b3

data = [1, 11, 2, 12, 4, 6, 13, 7, 8, 10]
k = 3
b1, b2, b3 = calculate(data)
c1 = b1
c2 = (b1**2 - b2) / 2
c3 = (b1**3 - 3*b1*b2 + 2*b3) / 6

# Коэффициенты полинома
coefficients = [1, c1, c2, c3]

# Вычисление корней (пропущенных чисел)
roots = np.roots(coefficients)

print(f"Сформировано кубическое уравнение: x**3 + {c1}x**2 + {c2}x + {c3}")
print(f"Найдены пропущенные числа: {roots[0] * -1:.0f}, {roots[1]* -1:.0f}, {roots[2]* -1:.0f}")

Как очевидно, при k > 3 (и при обработке больших массивов данных) нецелесообразно хардкодить формулы и держать все числа в памяти одновременно. Поэтому для k ≥ 4 и потоковой обработки данных используют другой подход, с рекуррентными формулами.

Общий случай

До сих пор для вычисления ожидаемых сумм степеней чисел мы использовали готовые формулы. Таких формул выведено немало, но по мере возрастания степени они становятся все более и более громоздкими:

Однако существует и общая формула – ее вывел в конце 17 века Якоб Бернулли:

Sk(n)=(n+B)k+1Bk+1k+1

Здесь B – соответствующее число Бернулли:

Что же касается коэффициентов (симметрических многочленов), то они определяются с помощью тождеств Ньютона. В примерах выше мы уже использовали эти формулы:

Общая формула выглядит так:

Как уже упоминалось выше, при обработке очень больших массивов данных целесообразнее использовать поточную вариацию алгоритма: тогда вычисления для входного потока данных можно делать рекуррентно, по мере поступления чисел, а вместо тождеств Ньютона использовать прямой подход к получению симметрических функций. Как реализовать этот алгоритм – разберем в следующей статье.

***

Статьи по теме

ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ

admin
11 декабря 2018

ООП на Python: концепции, принципы и примеры реализации

Программирование на Python допускает различные методологии, но в его основе...
admin
13 февраля 2017

Программирование на Python: от новичка до профессионала

Пошаговая инструкция для всех, кто хочет изучить программирование на Python...
admin
20 октября 2016

27 сайтов с задачками для оттачивания навыков программирования

<strong>Решение задач — хороший способ развить навыки разработки.</strong>