Для любого положительного n правило Коллатца задаёт следующий член как n / 2, если n чётное, и как 3n + 1, если n нечётное. Последовательность заканчивается, когда доходит до 1. Для 6 она такая: 6, 3, 10, 5, 16, 8, 4, 2, 1, то есть девять членов. Среди всех начальных чисел от 1 до limit найдите то, у которого членов больше всего.
Реализуйте longest_collatz_chain(limit).
У последовательностей общие окончания, поэтому, если запоминать найденную длину для каждого числа, работы станет намного меньше. Промежуточные члены могут превышать предел, так что используйте 64-битные целые.
Входные данные
limit: наибольшее начальное число, которое нужно проверить.
Выходные данные
Верните начальное число, последовательность которого содержит больше всего членов (считая само начальное число и завершающую 1). Если таких чисел несколько, верните наименьшее.
Ограничения
1 ≤ limit ≤ 100 000
Примеры
Ввод:
limit = 6
Ожидаемый вывод:
expected = 6
Ввод:
long long limit = 6;
Ожидаемый вывод:
long long expected = 6;
Ввод:
long limit = 6;
Ожидаемый вывод:
long expected = 6;
Пояснение
Длины последовательностей для чисел от 1 до 6: 1, 2, 8, 3, 6 и 9 членов, поэтому ответ 6.
Ввод:
limit = 10
Ожидаемый вывод:
expected = 9
Ввод:
long long limit = 10;
Ожидаемый вывод:
long long expected = 9;
Ввод:
long limit = 10;
Ожидаемый вывод:
long expected = 9;
Пояснение
9 даёт 20 членов (9, 28, 14, 7, ...), больше, чем любое другое начальное число до 10, поэтому ответ 9.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Сначала научитесь считать члены одной последовательности, включая начальное число и 1.
Подсказка 2
Когда последовательность доходит до числа, длина которого уже известна, прибавьте её вместо того, чтобы идти дальше.
Подсказка 3
Заменяйте лучшее начальное число, только если длина строго больше.
Ожидаемая сложность
время O(limit × average new steps), доп. память O(limit)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.