Question Link : Missing Number

Problem Statement:

You are given an array containing n distinct numbers taken from the range 0 to n. Find the one number that is missing from the array.

Example 1:

• Input: nums = [3, 0, 1]
• Output: 2
• Explanation: The numbers in the range are {0, 1, 2, 3}, and the missing number is 2.

Example 2:

• Input: nums = [0, 1]
• Output: 2
• Explanation: The numbers in the range are {0, 1, 2}, and the missing number is 2.

Constraints:

• n == nums.length
• 1 <= n <= 10^4
• 0 <= nums[i] <= n
• All the numbers of nums are unique.

Solution:

Approach:

The problem asks for the missing number from the array of natural numbers. A mathematical formula can help us solve it efficiently.

1. We use the well-known formula for the sum of the first N natural numbers:

Sum of N natural numbers= n(n+1)/2

1. By calculating the sum of the actual numbers in the array and comparing it to the expected sum from the formula, we can find the missing number as the difference between these two sums.

Example Walkthrough:
Let’s walk through an example with the array [3, 0, 1]:

• Using the formula:

Sum=3×(3+1)/2=6

• Calculating the sum of the array values:

Array Sum=3+0+1=4

• Therefore, the missing number is: 6−4 = 2

Performance:

• Time Complexity: O(N) — We iterate over the array once to calculate the sum.
• Space Complexity: O(1) — No extra space is used.

Code:

class Solution {
    public int missingNumber(int[] nums) {
        int sum = 0;
        for (int i : nums) sum += i;
        return (nums.length * (nums.length + 1) / 2) - sum;
    }
}

The above approach ensures that we can solve the problem in linear time with constant space, making it highly efficient for large datasets.

Leetcode 13 — Roman to Integer

Question Link : Roman to Integer

Problem Statement :

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

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

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.
• X can be placed before L (50) and C (100) to make 40 and 90.
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1:

Input: s = "III"
Output: 3
Explanation: III = 3.

Example 2:

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 3:

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints:

• 1 <= s.length <= 15
• s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
• It is guaranteed that s is a valid roman numeral in the range [1, 3999].

Solution:

Approach : Comparing the roman numbers with the next one

Firstly, we will implement the switch statements to calculate and get the value of the roman numberals. Then we will take integer value of each roman numberal from the input string and compare it with the integer value of the next roman numeral. If the next roman numberal is greater than the previous one then we will substract it from the total sum otherwise we will add it to the sum.

Explanation :

Before running the logic for the program, we used the System.gc() command to run the garbage collector in java and release the memory.

Now, we will define four variables as below :

1. sum= total sum of the integer values of each roman numeral

2. num= the current roman numeral value in the iteration.

3. next= the next roman numeral value after the current number.

4. strLength= the length of the roman number.

Note: We are defining variable for the string length outside the for loop so that the program only checks the length 1 time for the string. If we check the string length inside the for loop codition then it will check the String length for every iteration.

Now, we will use for loop to iterate over each character(roman numeral) in the roman number string. We will define a switch which will check the current index character and will assign it’s integral value to num variable. Similarly, the 2nd switch is defined for getting the integral value of the next character from the roman number string and store it in the next variable. Before the 2nd switch statement, we check if the current value of the iteration index is not the same as strLength— 1as it will cause an ArrayIndexOutOfBound Exception for the last iteration when there will be no next numeral.

Now, after getting the values of both the current and next roman numerals, we will check if the current number is less than next. If it’s less than next number then it means that we need to subtract that numeral value from the next roman number value or the sum . Else we can directly add the current number value to the sum variable.

Finally, at the end of the program we will return the total sum.

Performance :

Code :

class Solution {

    static {
        System.gc();
    }
    
    public int romanToInt(String s) {

        int sum=0;
        int num=0;
        int next=0;
        int strLength=s.length();

        for(int i=0; i<strLength;i++){

            switch(s.charAt(i)){
                case 'I' -> num = 1;
                case 'V' -> num = 5;
                case 'X' -> num = 10;
                case 'L' -> num = 50;
                case 'C' -> num = 100;
                case 'D' -> num = 500;
                case 'M' -> num = 1000;
            }
            if(i<strLength-1){
                switch(s.charAt(i+1)){
                    case 'I' -> next = 1;
                    case 'V' -> next = 5;
                    case 'X' -> next = 10;
                    case 'L' -> next = 50;
                    case 'C' -> next = 100;
                    case 'D' -> next = 500;
                    case 'M' -> next = 1000;
                }
            }

            if(num < next) sum-=num;
            else sum+=num;
        }

        return sum;
    }
}

Leetcode 9 — Palindrome Number Problem

Question Link : Palindrome Number

Problem Statement :

Given an integer x, return true if x is a palindrome, and false otherwise.

Example 1:

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Constraints:

• -231 <= x <= 231 - 1

Follow up: Could you solve it without converting the integer to a string?

Solution :

Approach :Reversing Half of the Number

Instead of reversing the entire number, we can reverse only the last half of the number. This approach is tricky because when we reverse the last half of the number, we don’t want the middle digit to be rev back to its original value. This can happen if the number has an odd number of digits. To resolve this, we can compare the first half of the number with the rev second half of the number.

Explanation :

We begin with an initial check to handle special cases:

If the input number x is negative, it cannot be a palindrome since palindromes are typically defined for positive numbers. In such cases, we immediately return false.
If x is non-zero and ends with a zero, it cannot be a palindrome because leading zeros are not allowed in palindromes. We return false for such cases.
We initialize two variables:

rev: This variable will store the rev second half of the digits of the number.
temp: This variable is a temporary placeholder to manipulate the input number without modifying the original value.
We enter a loop that continues until the first half of the digits (x) becomes less than or equal to the rev second half (rev):

Inside the loop, we extract the last digit of x using the modulo operator % and add it to the rev variable after multiplying it by 10 (shifting the existing digits to the left).
We then divide x by 10 to remove the last digit and move towards the center of the number.
Once the loop is completed, we have rev the second half of the digits. Now, we compare the first half of the digits (x) with the rev second half (rev) to determine if the number is a palindrome:

For an even number of digits, if x is equal to rev, then the number is a palindrome. We return true.
For an odd number of digits, if x is equal to rev / 10 (ignoring the middle digit), then the number is a palindrome. We return true.
If none of the above conditions are met, it means the number is not a palindrome, so we return false.
The code avoids the need for reversing the entire number by comparing only the necessary parts. This approach reduces both time complexity and memory usage, resulting in a more efficient solution.

Performance :

Code :

class Solution {
 public boolean isPalindrome(int x) {
 if (x < 0 || (x != 0 && x % 10 == 0))return false;
 int rev=0;
 int original=x;
 while(x>rev) {
 rev = rev*10+(x%10);
 x/=10;
 }
 return (x==rev) || (x==rev/10);
 }
}