Skip to main content

How to Check a Number is Fibonacci

If you have to check that given number is fibonacci number or not. You can check this by generating all fibonacci numbers until you get larger than given number But this take very much computation.

 You should use the following method.........

The given number is n
compute two numbers from n like this
a=(5*(n*n)+4)
b=(5*(n*n)-4)

If atleast one of them(a and b) is Perfect Square then the given number n must be Fibonacci Number.

Here a source code in Python.

def isPSqr(x):
    s=int(x**.5)
    return (s*s == x)
#print isPSqr(25)

def isFibo(n):
    return isPSqr(5*(n*n)+4) or isPSqr(5*(n*n)-4)
t=input()
while t:
    n=input()
    if isFibo(n):
        print 'isFibo'
    else:
        print 'isNotFibo'


    t-=1
Labels:

Comments

Post a Comment

Popular posts from this blog

com.mongodb.MongoCommandException: Command failed with error 18: 'Authentication failed.' on server

If you are trying to connect Mongo DB Server and it insanely throwing following error. com.mongodb.MongoTimeoutException : Timed out after 1000 ms while waiting for a server that matches ReadPreferenceServerSelector{readPreference=primary}. Client view of cluster state is {type=UNKNOWN, servers=[{address=192.168.1.10:27010, type=UNKNOWN, state=CONNECTING, exception={ com.mongodb.MongoSecurityException: Exception authenticating MongoCredential {mechanism=null, userName='user123', source='admin', password=<hidden>, mechanismProperties={}}}, caused by {com.mongodb.MongoCommandException: Command failed with error 18 : 'Authentication failed.' on server 192.168.1.10:27010 . The full response is { "ok" : 0.0, "code" : 18, "errmsg" : "Authentication failed." }}}] If you start looking the error content First you encounter with Timeout Exception which may mislead you. It is basically an authentication error. I...
5 comments
Read more

Easiest Method to Read and Write into Files Streams in Competitive Programming

                      T his article is about easiest way to perform read and write operation from file. File handling is one of the most important aspect of programming and it becomes more important when we do competitive programming. Here are some context when you need to deal with files in comptetive programming. 1) Some specific programming contests like Google Code Jam and Facebook Hacker Cup they provide a file for input. You have to read input from that file and write answers into a file and upload on server within limited time. 2) If you are trying to code for a problem. Suppose the problem was that a square matrix is given and you have to rotate the matrix by 90 degree clock-wise. First line of input indicate the total no. of test cases and first line before matrix represents size of matrix. Then input would be like this. 3 5 10 23 43 34 21 11 13 43 30 71 10 23 43 ...
4 comments
Read more

WARN AEROSPIKE_ERR_CLIENT Socket write error: 111

If you are just typing aql on terminal and following error throwing while your aerospike server has been started successfully. WARN AEROSPIKE_ERR_CLIENT Socket write error: 111 It may happen because you had connected some other server before, Now you are trying to connect to your localhost or different server. To remove the above error just type full command: aql -h 127.0.0.1 -p 3000                           ( put server ip in case of other server rather than localhost) instead of jus aql.
4 comments
Read more