Day 42 of DSA Problem Solving

Q1 :- Factorial of n

We are given a number n, and we need to compute its factorial, which is defined as:

n!=n×(n−1)×(n−2)×⋯×1

📈 Time and Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(n)

✅ Approach Explanation (Using Map)

• To find Factorial we use Recaration
• we use this Formula to Find Recaration n * Factorial(n - 1)

function Factorial(n){

  if(n === 1) return 1;

  return  n * Factorial(n - 1)

}

console.log(Factorial(5))

Q2 :-Find the Difference

• You're given two strings s and t, where string t is the same as string s with one additional character. You need to find and return that extra character.

✅ Approach

Use a Map to Count Characters in s:

• Create a Map called Obj to store how many times each character appears in string s.
• Loop through string s:
  • For each character, if it's already in the Map, increase its count by 1.
  • If it’s not in the Map, add it with a count of 1.
• This helps us keep track of how many times each character should appear.

Loop Through String t:

• For each character in string t, check if it exists in the Map:
  • If it does not exist or its count is 0, that means this is the extra character → return it immediately.
  • If it does exist, decrement the count by 1.

Return Default:

• If no extra character is found (which technically shouldn’t happen due to the problem constraints), return an empty string ''.

---

💡 Why Use a Map?

A Map is useful here because:

• It stores key-value pairs, where the key is the character, and the value is the count.
• Unlike arrays, Maps don’t have problems with non-numeric keys.
• Maps do not prevent duplicate keys—but they update values for existing keys, which is exactly what we want for counting.

---

⏱️ Time Complexity:

The algorithm loops through both strings s and t once:

• First loop: O(n)
• Second loop: O(n + 1)

Code

/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
var findTheDifference = function(s, t) {
    let Obj = new Map();


    for (let i = 0; i < s.length; i++) {
        Obj.set(s[i], (Obj.get(s[i]) || 0) + 1);
    }

    for (let j = 0; j < t.length; j++) {
        if (!Obj.get(t[j])) {
            return t[j]; // Not found or used up
        }
        Obj.set(t[j], Obj.get(t[j]) - 1);
    }

    return '';
};