Решение «респектабельной» проблемы бодрствования в одной строчке кода

Делать вещи простыми и эффективными.

СОДЕРЖАНИЕ

∘ Задача
∘ Понимание задачи
∘ Пошаговое выполнение
∘ Набор основных математических операций
∘ Перенос на Python
∘ Ссылки

Мне очень нравятся испытания Codility. Это прекрасный (и совершенно бесплатный) способ улучшить свои навыки решения проблем и знание языков программирования. Они также являются отличным способом «разогреть» ваш мозг для технических собеседований, тем более что большинство ваших решений оценивается по их способности справляться с крайними случаями, оставаясь при этом эффективными по времени.

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

За последние пару лет я медленно проработал их уроки и проблемы по выходным и праздникам, и это помогло мне сохранить настрой на поиск решений «жадного алгоритма» и рассмотрение как производительности, так и удобочитаемости.

Один конкретный урок застал меня врасплох. Задачи доброжелательности оцениваются в порядке сложности: «Безболезненно», «Уважительно» или «Амбициозно». Эта задача получила оценку «респектабельная», но ее можно эффективно решить с помощью одной строчки кода.

Задание

Уроки Codility состоят из материала для чтения в формате PDF и набора «задач». Первое задание урока «Суммы префиксов» называется «Подсчет Div». Инструкции следующие:

Напишите функцию ... которая для трех целых чисел A, B и K возвращает количество целых чисел в диапазоне [A..B], которые делятся на K

Гарантируется, что A ≤ B.

Понимание проблемы

Чтобы получить более полное представление о проблеме, я иногда нахожу полезным набросать ее, совершенно не беспокоясь об эффективности.

Очевидное решение методом перебора - перебрать все целые числа между A и B, проверяя, делятся ли они на K, используя по модулю (%).

Чтобы быть в безопасности, нам также нужно проверить, что B! = 0. В ruby:

def solution(a, b, k)
  return 0 if b == 0
  count = 0
  (a..b).each do |ii| 
    count += 1 if ii % k == 0
  end
  count
end

Или, что гораздо более кратко, используя тернарный оператор и filter, чтобы получить количество (размер) всех чисел, которые соответствуют нашим критериям:

def solution(a, b, k)
  b == 0 ? 0 : (a..b).filter{ |ii| ii % k == 0 }.size
end

Это будет выполняться за линейное время - O(n) - что неидеально, если A равно 0, а B - возможное максимальное значение теста в 2 миллиарда.

Итерация по шагам

Точно так же, как в приведенном ниже примере, нахождение наименьшего и наибольшего кратного k в диапазоне от A до B и повторение с шагом, равным K, по-прежнему оставляет нам O(n), что особенно неэффективно, если K равно 1.

def solution(a, b, k)
  return 0 if b == 0 || k > b
  first_divisible = a % k == 0 ? a : a + (k - a % k)
  last_divisible = b - b % k
  (first_divisible..last_divisible).step(k).size
end

Но мы близки к эффективному решению. Теперь мы можем видеть, что все, что нам нужно увидеть, это то, сколько раз кратное K встречается между A и B.

Набор основных математических операций

Давайте использовать исходный пример из Codility, a = 6, b = 11, k = 2.

• 11 / 2 = 5.5 - которое мы можем округлить до 5, чтобы получить общее количество способов, которыми 2 делится на 11
• (6 - 1) / 2 = 2.5 - которое мы можем округлить до 2 для количества способов, которыми целые числа меньше 6 делятся без остатка на 2. Мы можем вычесть их из суммы, указанной выше.
• 5 - 2 = 3 - вычтите исключенное количество из общего количества, чтобы получить наш результат.

В Ruby деление одного целого числа на другое автоматически округляет частное в меньшую сторону, возвращая целочисленный результат. Это делает наше решение аккуратным и эффективным, работающим с O(1) постоянным временем.

def solution(a, b, k)
  b / k - (a - 1) / k
end

Крайние случаи, когда A и / или B равны нулю, также аккуратно обрабатываются округлением вниз.

Перенос на Python

Разделение этажей Python (оператор «//») также может выполнить эту операцию за нас, хотя нам все равно нужно проверить, равно ли B 0.

def solution(a, b, k):
    return 0 if b == 0 else int(b // k - (a - 1) // k)

Любой из этих двух последних примеров все равно даст 100% результат на Codility.

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

использованная литература