DSA Problem Solving – Day 1

✅ Problem 1: Roman Numerals to Integer

🔖 Difficulty: Easy

🔗 Source: LeetCode #13

📘 Topic Tags: String, Hash Map, Math

---

🧠 Problem Description

Roman numerals are represented by seven symbols:

Symbol	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

Write a function to convert a Roman numeral into an integer.

💡 Rules:

• Roman numerals are usually written from largest to smallest.
• However, if a smaller number appears before a larger one, it must be subtracted.
• Example: IV = 4 (not IIII), IX = 9, XL = 40

🧾 Use this chart if you're unsure about how Roman numerals work:

🔗 Roman Numerals 1–100 Chart

---

🧩 Examples

Input: "III"      → Output: 3
Input: "IV"       → Output: 4
Input: "IX"       → Output: 9
Input: "LVIII"    → Output: 58  (50 + 5 + 3)
Input: "MCMXCIV"  → Output: 1994

Approach (Step-by-Step)

1. Create a map (object)

   • Store Roman letters and their integer values.

2. Loop through each character

   • Iterate over the input string one character at a time.

3. Compare the current character with the next one

   • Check if the next character's value is greater than the current character's value.

4. Subtraction case

   • If the next character is greater, subtract the current value from the total.

5. Otherwise, addition case

   • If the next character is not greater, add the current value to the total.

6. Return the total

   • After processing all characters, return the total integer value.

✅ JavaScript Solution

function romanToInt(s) {
  const roman = {
    I: 1,
    V: 5,
    X: 10,
    L: 50,
    C: 100,
    D: 500,
    M: 1000,
  };

  let total = 0;

  for (let i = 0; i < s.length; i++) {
    const currentVal = roman[s[i]];
    const nextVal = roman[s[i + 1]];

    if (nextVal > currentVal) {
      total -= currentVal;
    } else {
      total += currentVal;
    }
  }

  return total;
}

🧪 Test Cases

console.log(romanToInt("III"));      // 3
console.log(romanToInt("IV"));       // 4
console.log(romanToInt("IX"));       // 9
console.log(romanToInt("LVIII"));    // 58
console.log(romanToInt("MCMXCIV"));  // 1994

✅ Problem 2: Longest Common Prefix

🔖 Difficulty: Easy

🔗 Source: LeetCode #14

📘 Topic Tags: String, Array, Math ,loop

---

🧠 Problem Description

Write a function to find the longest common prefix string among an array of strings.

If there is no common prefix, return an empty string "".

💡 Constraints

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• Each strs[i] consists of only lowercase English letters (if it is non-empty).

⚙️ Approach (Step-by-Step)

1. Edge case check:
   
   If the input array is empty, return an empty string.

2. Assume the first string in the array is the initial common prefix.

3. Iterate through the rest of the strings in the array:

   • While the current string does not start with the prefix, shrink the prefix from the end (remove one character at a time).
   • If the prefix becomes an empty string during this process, return "".

4. Return the resulting prefix after checking all strings.

📥 Input

• An array of strings: strs[]

📤 Output

• A single string representing the longest common prefix.

🧪 Example

Input: strs = ["flower", "flow", "flight"]
Output: "fl"

Input: strs = ["dog", "racecar", "car"]
Output: ""

💻 JavaScript Solution:

var longestCommonPrefix = function(strs) {
    if (strs.length === 0) return "";

    let prefix = strs[0];
    for (let i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(prefix) !== 0) {
            prefix = prefix.substring(0, prefix.length - 1);
            if (prefix === "") return "";
        }
    }
    return prefix;
};

console.log(longestCommonPrefix(["flower", "flow", "flight"])); // Output: "fl"
console.log(longestCommonPrefix(["dog", "racecar", "car"]));    // Output: ""