Recursive Fibonacci Series with Memoization
Create a function “fib” that find the nth number in the Fibonacci series. while keeping a record of previously calculated Fibonacci numbers using memorization. Create another function, “fibMultiple(k, n)”, to find the nth multiple of k in the Fibonacci series.
Example: Finding the Position of nth Multiple of a Number in the Fibonacci Series using Recursion and Memoization in JavaScript
Javascript
// JavaScript function to find the position of // nth multiple of a number k in the Fibonacci // Series using recursion and memoization function fib(n, memo) { if (n === 1 || n === 2) { return 1; } if (memo[n] !== 0) { return memo[n]; } memo[n] = fib(n - 1, memo) + fib(n - 2, memo); return memo[n]; } function fibMultiple(k, n) { let memo = Array(100).fill(0); let count = 0; for (let i = 1; ; i++) { if (fib(i, memo) % k === 0) { count++; if (count === n) { return i; } } } } let k = 2; let n = 3; let result = fibMultiple(k, n); console.log(result); |
9
Time Complexity: O(N)
Space Complexity: O(N)
nth Multiple of a Number in Fibonacci Series in JavaScript
The Fibonacci series is a sequence of numbers where each number is the sum of the two previous ones, usually starting with 0 and 1. Given two integers n and k, the task is to find the position of the nth multiple of k in the Fibonacci series. For instance, if k = 2 and n = 3, the output would be 9 since the third multiple of 2 in the Fibonacci series is 34, which appears at position 9. There are multiple ways to find the nth multiple of a number in the Fibonacci series in Javascript which is as follows:
Table of Content
- Mathematical approach
- Iterative Approach using a List
- Recursive Fibonacci Series with Memoization