# Fibonacci

# Fibonacci

ezequiel + 0 comments A comment for Scala.

[SPOILER]

I used Long in Scala. For those having problems with overflow you may note that we are looking for

`fib(n) % (10**8 + 7)`

A nice property I used is that:

`(a + b) % n = (a % n + b % n) % n`

So, you can calculate and make a memo on fib(n)%(10**8+7) instead of using slower representations of big numbers. I passed all tests, but I wonder if the extra mods calculations are more efficient than the other solutions you mentioned.

- CB
chrisbeach + 2 comments What data types did Scala hackers use for this? My results overflowed a Long, so I used BigDecimal, but this didn't feel right.

- CB
chrisbeach + 0 comments saheb + 1 comment BigInt :) always works.

sourcedelica + 0 comments Mine timed out on the last test case using BigInt.

salman10862 + 0 comments That awkward moment when you realize you were supposed to use memoization.

Worked in Racket but I should redo this :/

Maybe tighten up the timing requirements for some of the languages? Small nitpick, still a valuable exercise.

- C
cyzhaa + 1 comment haskell

it looks ugly,but it does work..

fibs = 0 : 1 : zipWith (+) fibs (tail fibs) main = getContents >>= putStrLn.unlines.(map (show.(`mod` (10^8 + 7)).last.(flip take fibs).(+1).read)).tail.lines

- C
cyzhaa + 0 comments Does this question have some relationship with memoization or DP ? I think it's a recursion question.

zeotherm + 0 comments What is the timeout for this one? In F#, I can enumerate the answers for a Sequence from 0 to 10000 in just over 5 seconds on my laptop, yet I keep timing out on Test Case 3.

soooprmx + 1 comment how do I implement memoization in Haskell?

import Data.List fibos = take 10001 fibo 0 1 where fibo a b = a:(fibo b (a+b)) main = getLine >> getContents >>= putStrLn . unlines . map (show . fib . read) . lines where fib n = (flip mod (10^8+7)) . fibos !! n

- AS
ahmedrazasaeed + 0 comments I solved it by building a lazy list of fib numbers.

You can solve it without memoization by starting from 0 carrying the last two fib numbers with you.

fibHelper currentIndex desiredIndex currentFib prevFib =

something like that

- R
ravipemt + 0 comments I am running into timeouts constantly. Any clue?

wisn98 + 2 comments ## Haskell Solution

If you just gave up with Haskell, here is my solution. But, I think my solution is not really great.

fib :: Integer -> Integer fib n = fibz n [0, 0, 1] where fibz :: Integer -> [Integer] -> Integer fibz 0 (_:y:_) = y fibz n (x:y:z:(_)) = fibz (n - 1) [y, z, y + z] main :: IO () main = do n <- readLn :: IO Int l <- fmap (take n . lines) getContents :: IO [String] let x = map read l :: [Integer] output x output :: [Integer] -> IO () output [] = return () output (x:xs) = print ((fib x) `mod` 100000007) >> output xs

paulpach + 2 comments A better way that take advantage of lazy evaluation in haskell is to use infinite recursion to calculate the serie of all fibonacci numbers

-- this has all the fibonacci numbers and never ends -- [0, 1, 1, 2, 3, 5, 8, 13, 21 ... ] -- but haskell does not calculate them unless you actually -- ask for them. fib = serie 0 1 where serie i j = i : serie j (i+j)

Then if you want the nth fib, all you have to do is:

fib !! n

which is very efficient O(n)

- SB
stephen_berks056 + 1 comment You can get logarithmic time.

fib :: Int -> Integer fib n = snd . foldl_ fib_ (1, 0) . dropWhile not $ [testBit n k | k <- let s = finiteBitSize n in [s-1,s-2..0]] where fib_ (f, g) p | p = (f * (f + 2*g), ss) | otherwise = (ss, g * (2*f - g)) where ss = f*f + g*g foldl_ = foldl' -- '

paulpach + 0 comments Ughh, that code is very hard to read, do you have an explanation?

- AS
ahmedrazasaeed + 0 comments One liner:

fib = ((++) [0, 1] [fib (n-2) + fib (n-1) | n <-[2..] ] !!)

Though I presume your solution would be faster since it uses ":"

- BP
penkovsky + 1 comment Indeed, an infinite list is much more elegant in Haskell.

import Control.Monad ( replicateM_ ) dial :: [Int] -> IO () dial fibs = readLn >>= (pure . (fibs !!)) >>= print main = do -- Fibonacci list let fibs = let f x y = (x + y) `rem` 100000007 in 0 : 1 : (zipWith f fibs (drop 1 fibs)) readLn >>= flip replicateM_ (dial fibs)

aleksei_maide + 0 comments rem and mod arent exactly the same... not that it matters in this context :)

pbanavara + 1 comment So I used tail recursion in Scala and all test cases pass on my local machine. When I submit, TC 3 gives a runtime error. Any idea what could be the issue ? TC 3 runs fine on my local machine.

pbanavara + 1 comment Just messaged you my code.

doxuanthang + 0 comments Check my message :)

- ZP
Zpalmtree + 0 comments Not memoization but works fine.

import Control.Monad import Control.Applicative main = do n <- readLn mapM_ prettyprint =<< map (\x -> fibs !! x) <$> map read <$> replicateM n getLine fibs = 0 : 1 : zipWith (+) fibs (tail fibs) prettyprint n = print $ n `mod` 100000007

Sort 17 Discussions, By:

Please Login in order to post a comment