Все задачи
Средне Решено: 0 Процент решений: 0%

Число Капрекара

Проверьте, можно ли разрезать квадрат d-значного числа на левую часть и правую часть из d цифр так, чтобы их сумма равнялась исходному числу.

Чему вы научитесь

  • Разрезать число на левую и правую части по позиции цифры
  • Выбирать место разреза по количеству цифр n
  • Проверять все условия определения, включая ненулевую правую часть

Условие

Возведите число в квадрат и разрежьте десятичную запись квадрата на две части: правая часть состоит из последних d цифр, где d равно количеству цифр исходного числа, а левая часть из всего, что осталось (0, если ничего не осталось). Число называется числом Капрекара, если правая часть не равна нулю и сумма двух частей равна самому числу. Например, у 297 три цифры и 297² = 88209; правая часть равна 209, левая 88, и 88 + 209 = 297.

Реализуйте kaprekar_number(n).

В разных источниках определения различаются. Здесь разрез всегда делается ровно через d цифр от правого края (это вариант из OEIS A053816 и случай p = d в определении из Википедии); некоторые источники пробуют и другие места разреза, и тогда подходят числа вроде 4879, которые в этом варианте отвергаются. Правая часть может начинаться с нулей (для 703 получаем 703² = 494209, части 494 и 209) и не должна быть нулём, поэтому 10, 100, ... не являются числами Капрекара. Число 1 является числом Капрекара: 1² = 1 даёт левую часть 0 и правую 1.

Входные данные

n: проверяемое число.

Выходные данные

Верните true, если n является числом Капрекара в смысле определения выше, иначе false.

Ограничения

1 ≤ n ≤ 10^9

Примеры

Пример 1
Ввод:
n = 45

Ожидаемый вывод:
expected = True
Ввод:
long long n = 45;

Ожидаемый вывод:
bool expected = true;
Ввод:
long n = 45;

Ожидаемый вывод:
bool expected = true;

Пояснение

У 45 две цифры и 45² = 2025: левая часть равна 20, правая 25, и 20 + 25 = 45, поэтому ответ true.

Пример 2
Ввод:
n = 4879

Ожидаемый вывод:
expected = False
Ввод:
long long n = 4879;

Ожидаемый вывод:
bool expected = false;
Ввод:
long n = 4879;

Ожидаемый вывод:
bool expected = false;

Пояснение

У 4879 четыре цифры и 4879² = 23804641: левая часть равна 2380, правая 4641, и 2380 + 4641 = 7021, что не равно 4879, поэтому ответ false.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Пусть d равно количеству цифр n; храните n² в 64-битном целом.

Подсказка 2

При p = 10^d правая часть равна n² mod p, а левая равна n² / p.

Подсказка 3

Отвергайте число, если правая часть равна 0, даже если сумма совпадает.

Ожидаемая сложность

время O(d) для числа из d цифр, доп. память O(1)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.