Wednesday, 8 July 2020

Write a code to Check given number is a member of Fibonacci series or not

                   Fibonacci Member

Problem Description: You are given with a number N, you have to figure out if it is a member
of Fibonacci series or not. Return true if the number is member of Fibonacci series else false.

How to approach?
We can approach this problem by generating Fibonacci numbers till generated numbers are less
than N.

If the generated number is equal to N, then it is a member of Fibonacci series, otherwise not.

Pseudo Code for this problem:
Input=N
Function checkMember:
a=0
b=1
While a less than N:
 c=a + b
 a=b
 b=c
If a equal to N:
 Return true
Else:
 Return false

❏ Let us dry run the code for N= 5
a=0
b=1

    ➔ a < N :
        c=0+1= 1
        a= 1
        b= 1

   ➔ a < N :
       c=1+1= 2
       a= 1
       b= 2

  ➔ a < N :
      c=1+2= 3
      a= 2
      b= 3

  ➔ a < N :
      c=2+3= 5
      a= 3
      b= 5

  ➔ a < N :
      c=3+5= 8
      a= 5
      b= 8

  ➔ a = N
    Return true

   Final output:
   true

Given a number N, figure out if it is a member of fibonacci series or not. Return true if the number is member of fibonacci series else false.
Fibonacci Series is defined by the recurrence
    F(n) = F(n-1) + F(n-2)
where F(0) = 0 and F(1) = 1

CODE:

f = 0
s = 1
t = 1

def checkMember(n):

    global f
    global s
    global t
    while t <= n:
      t = f + s
      f = s
      s = t
      if f == n:
        return 1
    pass

n=int(input())

if(checkMember(n)):
    print("true")
else:
    print("false")


Input Format :
Integer N
Output Format :
true or false

Constraints :
0 <= n <= 10^4

Sample Input 1 :
5
Sample Output 1 :
true

Sample Input 2 :
14
Sample Output 2 :
false