We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Fundamentals
  4. Is Fibo
  5. Discussions

Is Fibo

Sort by

recency

|

388 Discussions

|

  • jmcparland
     + 0 comments

    Haskell

    module Main where

import Control.Monad (replicateM_)
import qualified Data.Set  as S

fibos :: S.Set Integer
fibos = S.fromList $ takeWhile (<= 10000000000) fibos'
  where
    fibos' = 1 : 1 : zipWith (+) fibos' (tail fibos')

main :: IO ()
main = do
    cases <- readLn :: IO Int
    replicateM_ cases $ do
        n <- readLn :: IO Integer
        putStrLn $ if n `S.member` fibos then "IsFibo" else "IsNotFibo"

  • firaskhalfallah1
     + 0 comments

    here is my solution ! very time efficient without using lists

    def isFibo(n):
    # Write your code here
    if n==0 or n==1:
        return "IsFibo"
    i_th=0
    i2_th=1
    index=1
    while index<=n:
        if i_th+i2_th==n:
            return "IsFibo"
        i_th = i2_th
        i2_th = index
        index = i_th + i2_th
    if index==n:
        return "IsFibo"
    return "IsNotFibo"

  • runeforce1
     + 0 comments

    the problem is actually quite easy. the bigger problem is how to handle the time limit. that's where we needed the "cache". golang map is excellent in this

    Golang :

    var fiboVal = make(map[int64]int64)

func isFibo(n int64) string {
    // Write your code here
    var isFiboVar = make(map[int64]bool)
    
    if _, isExist := isFiboVar[0]; !isExist {
        isFiboVar[0] = true
    }
    
    if _, isExist := isFiboVar[1]; !isExist {
        isFiboVar[1] = true
    }
    
    for i := int64(2);;i++ {
        val := fibo(i)
        isFiboVar[val] = true
       
        if val > n {
            break
        }
    }

    if isFiboVar[n] {
        return "IsFibo"
    }

    return "IsNotFibo"
}

func fibo(n int64) int64 {
    if _, isExist := fiboVal[n]; isExist {
        return fiboVal[n]
    }
    
    if n == 0 {
        fiboVal[0] = 0
        return 0
    }
    
    if n == 1 {
        fiboVal[1] = 1
        return 1
    }
    
    if n > 1 {
        fiboVal[n] = fibo(n-1) + fibo(n-2)
        return fiboVal[n]
    }
    
    return 0
}

  • siddhanthbiswas
     + 0 comments
    import os


def get_fibs():
    maxi = 10 ** 10
    first, last = 1, 1
    fibs = [first, last]
    while last <= maxi:
        last_new = first + last
        fibs.append(last_new)
        first = last
        last = last_new
    return fibs

def isFibo(fibs, n):
    Y, N = "IsFibo", "IsNotFibo"
    if n in fibs:
        return Y
    else:
        return N

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input().strip())
    
    fibs = get_fibs()

    for t_itr in range(t):
        n = int(input().strip())
        
        result = isFibo(fibs, n)

        fptr.write(result + '\n')

    fptr.close()

  • gordonlu310old
     + 0 comments

    C++ solution. This instructs the compiler to precompute the first 50 Fibonacci numbers, enough to satisfy the constraints.

    #include <bits/stdc++.h>

using namespace std;

constexpr array<long long, 50> compute() {
    array<long long, 50> fiboNums = {1, 1};
    long long fib1 = 1, fib2 = 1;
    for (int i = 2; i < 50; i++) {
        long long newFib = fib1 + fib2;
        fib1 = fib2, fib2 = newFib;
        fiboNums[i] = fib2;
    }
    return fiboNums;
}

array<long long, 50> fiboNums = compute();

void solve() {
    long long n;
    cin >> n;
    
    if (*lower_bound(fiboNums.begin(), fiboNums.end(), n) != n)
        cout << "IsNotFibo" << endl;
    else
        cout << "IsFibo" << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
        
    int t;
    cin >> t;
    
    while (t--)
        solve();
    
    return 0;
}