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
Mathematical approach
The Fibonacci series has a repeating pattern. We can use this pattern to quickly figure out where the nth multiple of a number k is in the series by using a specific math method to recognize when a Fibonacci number is a multiple of k.
Example: The Position of nth Multiple of a Number in the Fibonacci Series using an Iterative Approach in JavaScript.
Javascript
// JavaScript function to find the position of // nth multiple of a number k in the Fibonacci Series function findPosition(k, n) { let f1 = 0; let f2 = 1; let i = 2; while ( true ) { let f3 = f1 + f2; f1 = f2; f2 = f3; if (f2 % k === 0) { return n * i; } i++; } } let n = 5; let k = 4; console.log( "Position of nth multiple of k in Fibonacci Series is" , findPosition(k, n) ); |
Position of nth multiple of k in Fibonacci Series is 30
Time Complexity: O(N)
Space Complexity: O(1)
Iterative Approach using a List
Another approach involves generating the Fibonacci series and checking for multiples of k. This function iteratively generates the Fibonacci series and checks for multiples of k.
Example: Finding the Position of nth Multiple of a Number in the Fibonacci Series using Iterative Approach in JavaScript.
Javascript
// JavaScript function to find the position // of nth multiple of a number k in the // Fibonacci Series using an iterative approach function nthFibMultiple(n, k) { let fibonacci = [0, 1]; let counter = 0; for (let i = 2; ; i++) { let current = fibonacci[i - 1] + fibonacci[i - 2]; if (current % k === 0) { counter++; if (counter === n) { return i; } } fibonacci.push(current); } } console.log(nthFibMultiple(3, 2)); |
9
Time Complexity: O(N)
Space Complexity: O(N)
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)