Roman To Integer

Problem Statement

Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999

Programming Language: C#
Run Time Complexity: O(N)
Space Complexity: Constant space
Resources: http://en.wikipedia.org/wiki/Roman_numerals
Source: https://leetcode.com/problems/roman-to-integer/
Solution

public int RomanToInt(string s)
{
    // Input validation
    if (string.IsNullOrEmpty(s))
        return 0;

    // 4:IV, 9:IX, 40:XL, 90:XC, 400:CD, 900:CM,
    // 1:I, 10:X, 100:C, 1000:M
    int output = 0;
    // Prev is previous character in the input string
    char pre = ' ';

    for (int i = 0; i < s.Length; i++)
    {
        if (s[i] == 'M' && pre != 'C') { output += 1000; }
        if (s[i] == 'C' && pre != 'X') { output += 100; }
        if (s[i] == 'X' && pre != 'I') { output += 10; }

        if (s[i] == 'M' && pre == 'C') { output += 800; }
        if (s[i] == 'C' && pre == 'X') { output += 80; }
        if (s[i] == 'X' && pre == 'I') { output += 8; }

        if (s[i] == 'I') { output += 1; }

        if (s[i] == 'V' && pre != 'I') { output += 5; }
        if (s[i] == 'L' && pre != 'X') { output += 50; }
        if (s[i] == 'D' && pre != 'C') { output += 500; }

        if (s[i] == 'V' && pre == 'I') { output += 3; }
        if (s[i] == 'L' && pre == 'X') { output += 30; }
        if (s[i] == 'D' && pre == 'C') { output += 300; }

        pre = s[i];

    }

    // Return output
    return output;
}

Integer to Roman

Problem Statement

Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.

Programming Language: C#
Run Time Complexity: O(N)
Space Complexity: Constant space
Resources: http://en.wikipedia.org/wiki/Roman_numerals
Source: https://leetcode.com/problems/integer-to-roman/

Solution

public string IntToRoman(int num)
{
    // Maintain a mapping of numbers to roman numerals staring from highest numeral
    int[] integer = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
    String[] roman = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
    
    // Output 
    string output = "";

    // Input validation (Num should be in the range of 1-3999)
    if (num <= 0)
        return output;

    for (int index = 0; index < integer.Length; index++)
    {
        int result = num / integer[index];

        // Append the roman numeral equal to the result 
        while (result > 0)
        {
            output += roman[index];
            result--;
        }

        // Continue the processing with the remainder
        num = num % integer[index];
    }

    // return output
    return output;
}

Palindrome Number

Problem Statement

Determine whether an integer is a palindrome. Do this without extra space.

Source: https://leetcode.com/problems/palindrome-number/

Programming Language: C#
Run Time Complexity: O(N)(Number of digits in the input)
Space Complexity: Constant space for divider

public bool IsPalindrome(int x)
{
    // Input validation -ve number is not palindrome number
    if (x < 0)    
        return false;    

    // Set divider to 1 
    int divider = 1;

    // While the number of digits in divider is eual to the number of digits of input
    while (x / divider >= 10)
    {
        divider *= 10;
    }

    // While input is not equal to 0
    while (x != 0)
    {
        // Take the right most digit
        int right = x % 10;

        // Take the left most digit
        int left = x / divider;
        
        // Not a palindrome number if left and right digit not match
        if (right != left)        
            return false;
        
        // input equal to mod of divider to get the number skipping left most digit
        x %= divider;
        
        // input divide by 10 to skip the right most digit
        x /= 10;
        
        // divider should be reduced by factor of 100 since right and left most digits are processed
        divider /= 100;
    }

    // Input validated and is palindrome number return true
    return true;
}

Add Two Numbers

Problem Statement

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

 

Source: https://leetcode.com/problems/add-two-numbers/

Programming Language: C#
Run Time Complexity: O(N)
Space Complexity: Constant space

 

Solution 

 

 

// List Node Structure 
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; }
}

public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
{
    int carry = 0;
    // Create a dummy node as a start of new List
    ListNode newHead = new ListNode(0);
    // Pointers to respective list
    ListNode p1 = l1, p2 = l2, p3 = newHead;
    
    // While list 1 and list 2 are processed
    while (p1 != null || p2 != null)
    {
        if (p1 != null)
        {   
            
            carry += p1.val;
            p1 = p1.next;
        }

        if (p2 != null)
        {
            carry += p2.val;
            p2 = p2.next;
        }

        p3.next = new ListNode(carry % 10);
        p3 = p3.next;
        // If the result exceeds 10 keep track of carry
        carry /= 10;
    }
    
    // if carry is 1 create a new node 
    if (carry == 1)
        p3.next = new ListNode(1);

    // Return dummy nodes next 
    return newHead.next;
}

Reverse Integer

Problem Statement

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

 

Have you thought about this? Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!
If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.
Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Source: https://leetcode.com/problems/reverse-integer/
Programming Language: C#

Solution
 

public int Reverse(int x)
{
    bool isNeg = false;
    long result = 0;
    
    // Check if the number is negative   
    if (x < 0)
    {
        isNeg = true;
        x *= -1;
    }
    
    // While number is processed
    while (x > 0)
    {   
        // Grab the last digit from mod operation and add to result
        result = result * 10 + (x % 10);
        
        // If there is int overflow return 0   
        if (result >= Int32.MaxValue)
            return 0;

        x = x / 10;
    }
    
    // if number is negative update the sign
    if (isNeg)
        result *= -1;
    

    // cast it to int and return
    return (int)result;
}