🚀 Day 36 of DSA Problem Solving

Q.no 1 :- Fibonacci Number

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones. That is:

F(n)=F(n−1)+F(n−2) 

For example:

F(0) = 0 F(1) = 1 F(2) = 1 F(3) = 2 F(4) = 3 F(5) = 5 F(6) = 8 

⚙️ Approach

To compute the Fibonacci number at position n:

• If n is 0 or 1, we return the value directly. These are the base cases.
• Otherwise, we recursively calculate the values of fib(n-1) and fib(n-2) and return their sum.
• This approach naturally mimics the Fibonacci definition.

✅ Base Cases

These are the stopping conditions for our recursion:

• If n == 0, return 0
• If n == 1, return 1

Without base cases, the recursion would go infinitely deep and eventually crash.

Complexity

Time complexity: O(2n)

• This is because each function call makes two more calls, resulting in a binary tree of calls. This causes an exponential growth in the number of calls.

Space complexity: O(n)

This is due to the maximum depth of the recursion stack, which goes as deep as n.

Code

/** * @param {number} n * @return {number} */ var fib = function(n) { if(n === 0) return 0 if(n === 1) return 1 let sum = fib(n-2) + fib(n-1) return sum }; 

Question 2: Count and Say

Approach

This problem is solved using recursion.

The key idea is to generate the result for n by building upon the result of n-1.

• Start with the base case where n = 1, which is "1".
• For each subsequent value of n, we "read" the previous string and construct the new one:
  • Count consecutive identical digits.
  • Append the count followed by the digit to the result.
• This process is repeated recursively until the required term is built.

Base Case

• When n === 1, return "1" as the starting term of the sequence.

Time Complexity

• Time Complexity: O(2^n) in the worst case.
  • The length of each term may be up to twice the length of the previous one.
  • Each recursive call processes the entire previous string.
• Space Complexity: O(2^n) due to recursive calls and string building.

Code

/** * @param {number} n * @return {string} */ var countAndSay = function(n) { if (n === 1) return "1"; // Base case const prev = countAndSay(n - 1); // Recursive call let result = ""; let count = 1; for (let i = 1; i <= prev.length; i++) { if (prev[i] === prev[i - 1]) { count++; } else { result += count.toString() + prev[i - 1]; count = 1; } } return result; };