PROBLEM LINK:
THE STARK INTERNSHIP !
PROBLEM CODE: MARVELDC
DIFFICULTY: medium
On the keen observation of the test cases, one could find out that if the given number is a fibonacci-prime print ‘Green’ else print ‘Red’.
Now there are two possible approaches to solving this question.
One straightforward solution would involve checking if the number is a fibonacci or a prime but since the question required an optimal solution, on should precompute all the fibonacci numbers <= 10^18. The pre-computation of primes upto 10^18 is not feasible as sieve of Eratosthenes cannot be used for such large numbers. Hence the property that “Every composite number will have at-least one factor <= sqrt(number)” can be used for checking of primes. Again a small observation points out that checking whether a number is fibonacci or not is faster than prime checking and hence the numbers should be checked for fibonacci and then checked for prime. The author’s solution is also implemented with the same idea.
Time complexity: O(n)
Another clever solution would be the most efficient one to this question. Since there are only 12 fibonacci prime numbers within the given constraint, one can just store the 12 numbers in an array and check whether the number is present in the array or not to print ‘Green’ or ‘Red’ respectively.
Time complexity: O(1)
Setter’s solution: Solution