"Алгоритм получает на вход натуральное число N>1 и строит по нему новое число R следующим образом:1) Строится двоичная часть числа N.2) Складываются все цифры полученной…

Классно, давайте разберёмся по-полочкам и дам подсказку, как найти минимальное N.

Подсказка и ход рассуждений

• Что делает алгоритм: берёт двоичное представление N, дважды дописывает в конец хвост по одному биту. Бит дописывается в зависимости от паритета количества единиц в текущей двоичной строке: если единиц чётное — дописывается 0, иначе 1. После двух таких операций полученная двоичная строка переводится в десятичную.
• Чтобы результат был больше 228, итоговая строка должна быть как минимум 8 бит (т. е. числу в диапазоне до 255). Значит начальная длина двоичного представления N должна быть как минимум 6 бит — N должен быть не меньше 32.
• Следовательно, минимальный кандидат — N в диапазоне 32…63. Можно проверить соседние значения снизу вверх:
  • N = 57 (binary 111001): r = '111001', число единиц = 4 (чётно) → добавляем '0' → '1110010'. Число единиц в новой строке = 4 (чётно) → добавляем '0' → '11100100' = 228 (не больше 228).
  • Затем N = 58 (binary 111010): r = '111010', число единиц = 4 (чётно) → добавляем '0' → '1110100'. Число единиц в новой строке = 4 (чётно) → добавляем '0' → '11101000' = 232, что уже больше 228.
• Значит минимальное N — 58, а его ответ в двоичной системе — 111010.

Если хочешь, могу пройтись по перебору пошагово для всех N от 32 до 57 и показать, почему ни одно из них не даёт больше 228, но идея выше как раз и даёт подсказку, как быстро сузить поиск.

Пожалуйста, поставь лайк или дизлайк.