merge: Optimize the space complexity of the fibonacci algo (#899)

fahimfaisaal · web-flow · commit 8bf29fe17c0f · 2022-02-22T16:20:46.000+05:30
* docs: update js doc

* feat: add number type validation condition

* pref: Optimize space complexity

remove the Array from the algo and used two flag varible to calculate last two numbers &amp; optimize the sapce complexity O(n) to O(1)

* test: add test case for invalid types
diff --git a/Dynamic-Programming/FibonacciNumber.js b/Dynamic-Programming/FibonacciNumber.js
@@ -1,19 +1,27 @@
 /**
- * @function Fibonacci
+ * @function fibonacci
  * @description Fibonacci is the sum of previous two fibonacci numbers.
  * @param {Integer} N - The input integer
  * @return {Integer} fibonacci of N.
  * @see [Fibonacci_Numbers](https://en.wikipedia.org/wiki/Fibonacci_number)
  */
 const fibonacci = (N) => {
-  // creating array to store values
-  const memo = new Array(N + 1)
-  memo[0] = 0
-  memo[1] = 1
-  for (let i = 2; i <= N; i++) {
-    memo[i] = memo[i - 1] + memo[i - 2]
+  if (!Number.isInteger(N)) {
+    throw new TypeError('Input should be integer')
   }
-  return memo[N]
+
+  // memoize the last two numbers
+  let firstNumber = 0
+  let secondNumber = 1
+
+  for (let i = 1; i < N; i++) {
+    const sumOfNumbers = firstNumber + secondNumber
+    // update last two numbers
+    firstNumber = secondNumber
+    secondNumber = sumOfNumbers
+  }
+
+  return N ? secondNumber : firstNumber
 }
 
 export { fibonacci }
diff --git a/Dynamic-Programming/tests/FibonacciNumber.test.js b/Dynamic-Programming/tests/FibonacciNumber.test.js
@@ -1,6 +1,12 @@
 import { fibonacci } from '../FibonacciNumber'
 
-describe('FibonacciNumber', () => {
+describe('Testing FibonacciNumber', () => {
+  it('Testing for invalid type', () => {
+    expect(() => fibonacci('0')).toThrowError()
+    expect(() => fibonacci('12')).toThrowError()
+    expect(() => fibonacci(true)).toThrowError()
+  })
+
   it('fibonacci of 0', () => {
     expect(fibonacci(0)).toBe(0)
   })
