Check if digits in a number can be rearranged to form a fibonacci number

user_5524175 0
Viewed 170

This question is asked in a programming contest. I couldn't find any way other than generating all permutations. But the number of digits is upto 15 and no of permutations (15!) is very large. Is there any other way?

I know that if (5*N^2 + 4) or (5*N^2 - 4) is a perfect square, n is fibonacci.

fibonacci algorithm string
1 Answers

You don't need to generate all permutations. Generate the fibonacci numbers of desired length (which will be less than 74 numbers, because 73rd fib. number is the highest with 15 digits) and then just check for those few whether they can be "constructed" from digits in the given number.

user_40051750
Related