HackerRank ‘Is Fibo’ Solution

H
Short Problem Definition:

You are given an integer, N. Write a program to determine if N is an element of the Fibonacci sequence.

Link

Is Fibo

Complexity:

time complexity is O(15√(ϕn−(−ϕ)−n))

space complexity is O(15√(ϕn−(−ϕ)−n))

Execution:

There are two methods:

A) generate all fibonacci numbers up to N and check if the candidates are in this set.

B) There is a mathematical function that can prove whether a number is in the Fibonacci sequence in sqrt(N) time. I am not going to explain this here. Read the discussion on SO if you are interested.

Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#!/usr/bin/py
def getFibo(N):
    v = [1,2]
    while v[-1] < N:
        v.append(v[-1]+v[-2])
     
    return set(v)
 
def isFibo(fiboSet, value):
    if value in fiboSet:
        return "IsFibo"
    return "IsNotFibo"
 
if __name__ == '__main__':
    t = input()
    values = []
    for _ in xrange(t):
        values.append(input())
     
    fiboSet = getFibo(max(values))
     
    for value in values:
        print isFibo(fiboSet, value)

About the author

Add comment

Archives

Categories