В этом посте рассматривается проблема подсчета количества элементов, остаток которых равен 0 при делении на определенное значение в заданном массиве.
Описание задания
Напишите функцию:
решение по определению (A, B, K)
что для трех целых чисел A, B и K возвращает количество целых чисел в диапазоне [A..B], которые делятся на K, т. е.:
{ i : A ≤ i ≤ B, i mod K = 0 }
Например, для A = 6, B = 11 и K = 2 ваша функция должна вернуть 3, потому что в диапазоне [6..11] есть три числа, делящихся на 2, а именно 6, 8 и 10.
Напишите эффективный алгоритм для следующих предположений:
- A и B — целые числа в диапазоне [0..2 000 000 000];
- K — целое число в диапазоне [1..2 000 000 000];
- A ≤ B.
Авторские права, 2009–2020 гг., принадлежат Codility Limited. Все права защищены. Несанкционированное копирование, публикация или разглашение запрещено.
Ключевой момент
- При линейном поиске дальнего массива затраты времени будут больше.
- После деления 0 на любое значение получается 0.
Решение (с использованием Python)
def solution(A, B, K):
bound_1, bound_2 = (A / K), (B / K) // 1
if(bound_1 != 0 and bound_1 % 1 == 0): bound_1 -= 1
bound_1 = bound_1 // 1
answer = max(int(bound_2 - bound_1), 0)
if(A == 0): answer += 1
return answer
Используйте приведенное выше решение для справки.
Я рекомендую вам написать собственный исходный код.
