Ctrl K

Самая большая группа равных после сдвигов

Средняя
Дан массив целых чисел values и число reach. Каждый элемент можно не больше одного раза заменить любым целым числом из отрезка [values[i] - reach, values[i] + reach]. После таких замен выберите как можно больше элементов (в любых позициях), которые равны между собой. Верните наибольшее возможное число таких элементов.
Пример 1
values=[3, 11, 8, 15], reach=2 → 2

8 и 11 можно сдвинуть к 10 (или 9), а вот троих одинаковыми не сделать: у 8 и 15 разница 7, больше чем 2 · 2. Ответ 2.

Пример 2
values=[1, 10, 4, 7], reach=3 → 3

1, 4 и 7 превращаем в 4: первое сдвигаем на +3, третье на -3. Достать до них 10 уже не получится.

Пример 3
values=[6], reach=0 → 1
Ограничения
  • 1 ≤ len(values) ≤ 10⁵
  • 0 ≤ values[i] ≤ 10⁵
  • 0 ≤ reach ≤ 10⁵
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиk ближайших значений СредняяПодравнять числа прибавлением СредняяКовёр на окрашенные отрезки СредняяЗаделать пробелы одним отрезком СредняяПодвинуть числа навстречу Средняя
загружаем Python…
Вход
values=[3, 11, 8, 15], reach=2
Ожидается
2

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 122 теста на сервере, включая скрытые.