🚀 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;
};