Проверьте, можно ли переставить цифры в числе, чтобы сформировать число Фибоначчи

Question

Этот вопрос задается в конкурсе по программированию.Я не мог найти ничего, кроме генерации всех перестановок.Но количество цифр до 15, и ни одна из перестановок (15!) Не очень велика.Есть ли другой способ?

Я знаю, что если (5 * N ^ 2 + 4) или (5 * N ^ 2 - 4) - идеальный квадрат, то n - это Фибоначчи.

Answer 1

Вам не нужно генерировать все перестановки.Сгенерируйте числа Фибоначчи желаемой длины (которые будут меньше, чем 74 числа, потому что 73-е число фиб. Является наибольшим с 15 цифрами), а затем просто проверьте эти немногие, могут ли они быть «построены» из цифр в данном номере.