Algorithm and Data Structure ( Add Two Numbers In Linked List)

     Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. 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.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Method 1:
   
This problem is straightforward where we need to traverse both the list simultaneously till we
reach the end of both the list.
Then we need to add the value of each respective node say x+y along with any carry.
Initialize carry with 0.
sum = x+y+carry

Create a new node and add sum Mod 10 as the value of the new node.
Update carry = sum/10

E.g   2 + 5 = 7  carry = 0, new node = 7,
        4+6= 10, carry=1, new node =0,
        3+4+1(carry), carry = 0, new node = 8

Output : 7=>0=>8

Remember to check any carry left after you traverse both the list till the end.
If carry > 0 then create a new node with carry as node value.

Implementation :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */

 public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
       
       ListNode head = new ListNode(0); // dummy node
       ListNode output = head;
       int carry = 0;
       int sum=0;
           
            while (l1!= null || l2!= null)
            {
                sum = carry; // in each iteration initialize sum with any carry left
                if (l1 != null)
                {
                    sum +=  l1.val; // add node  value in sum
                    l1 = l1.next;  // move list1
                }
                if (l2 != null)
                {
                    sum+= l2.val; // add node  value in sum
                    l2 = l2.next;   // move list2
                }
              
                carry = sum/10;  // find any carry
                output.next = new ListNode(sum % 10); // create a new node with value
                output = output.next;
               
               
            }
             
                if (carry!=0)  // if any carry left than add it as new node value
                {
                     output.next = new ListNode(carry);
                     output = output.next;    
                }

            return head.next; // head is a dummy node whose next points to out output list.
       
    }

Time Complexity: O(max(m,n)) where m and n is the size of lists.
Space Complexity : O(max(m,n) + 1), here +1 is for any carry if left.

Method 2 :

There are other ways also where you traverse each list and form the number.
After forming the number, you add the two numbers and create the list in reverse order.
For forming the number you can use place value of each number in list

e.g 2=>4=>3 

2 * 10^0 + 4* 10^1 + 3* 10^2 = 2 + 40 + 300 = 342 

5 * 10^0 + 6* 10^1 + 4* 10^2 = 5 + 60 + 400 = 465 
                                                                     sum= 807

Create the list for each digit from sum in reverse order 7=>0=>8

Time Complexity : O(max(m,n)) +  O(max(m,n) + 1) where m and n is the size of lists.

= 2O(max(m,n))+1

Time is twice because first, we create the respective sum for each list in O(max(m,n)) and then
 break the sum in O(max(m,n)+1) time for creating output list.

Space Complexity : O(max(m,n) + 1), here +1 is for any carry if left.

                  

Algorithm and Data Structure (Two Number)

Two Number

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
There can be duplicate elements in the array of integers. If your solutions have one of this element than consider the position of the first element.
If no such elements exist then return [-1,-1].

Given input = [1, 3, 6, 8, 2], target = 10,

Because input [3] + input [4] = 8 + 2 = 10,
Output : [3, 4].

Do not use the element with same position twice.
e.g input = [2, 7, 2, 8, 6], target = 4
Output =[0,2] is correct, where index 0 and 2 both has element 2 but in different position.
Output= [0,0] is wrong. Here we are repeating the element with the same position.

Method 1 (Brute Force):

We can use brute force approach to solve this problem. We take each element and add with
other elements in the array and check if their sum is equal to the target value.
If we have such sum than we break from the loop and return the positions in the array.

Implementation(c#) :

     public int[] TwoSum(int[] input, int target)
        {
        
              for(int i=0;i<n-1;i++)
                {
                     for(int j=i+1;j<n;j++)
                       {
                          if(input[i]+input[j] == target)
                           return new int[]{i,j};
                        }
                }
               return new int[]{-1,-1};
         }

Time Complexity is O(n-1) * O(n) = O(n^2).
Space Complexity is O(1).

Method 2 (Sorting): First we can sort the array using MergeSort which has the time complexity of      O(n Log n) in all best, worst and average case.
After sorting we will run a loop  and find pair of elements as shown below :

      if input[i]+ input[n-1] == target , n is the length if the array.
        a = input[i];
        b = input[n-1]

     if input[i]+ input[n-1] > target
        n--;

     else
        i++

Input = [1, 3, 6, 8, 2 ], target = 10

After Sorting : [1,2,3,6,8], i=0, n=5
Now check if input[i]+input[n-1]
i.e 1+8=9<10 so increase I
      2+8 =10 so assign 2 and 8 to some temporary variable;

Now try to find their actual position in the original unsorted input array and return their actual positions in sorted order.

Remember to keep a copy of the original input.

Time Complexity =  O(n log n)
Space Complexity = O(n) + O(n) +2C = O(2n)

Implementation

public int[] TwoSum(int[] nums, int target)
        {
            var nums1 = (int[])nums.Clone(); // copy of original input
            var result = new int[2]{-1,-1};
            Array.Sort(nums);
            int a = 0, b = 0;
            int n = nums.Count();
            int i = 0;
            while (i < n)
            {
                if (nums[i] + nums[n - 1] == target)
                {
                    a = nums[i];
                    b = nums[n - 1];
                    break;
                }
                else if (nums[i] + nums[n - 1] > target)
                    n--;
                else
                    i++;
            }
            int apos = -1, bpos = -1;
            i = 0;
             n = nums.Count();
            while (i < n)
            {
                if (apos == -1 && a == nums1[i])
                {
                    apos = i;
                    i++;
                }
                  
                if (bpos == -1 && b == nums1[i])
                    bpos = i;
                if (apos != -1 && bpos != -1)
                    break;
                i++;
            }
            if (apos <= bpos)
            {
                result[0] = apos;
                result[1] = bpos;
            }
            else
            {
                result[1] = apos;
                result[0] = bpos;
            }  
          
            return result;
        }

Method 3 (Hash Table) :

Using the hash table to solve this problem will be the best approach.
Here we will create a hash table with a key as the number and its index as the value in the input array.
Then check if the target- input[i] is present in the table or not.

E.g target = 10, input[i] starting from 1 in array [1,3,6,8,2]
                                                                                                   hashtable(number,position)
check 10-1 =9 is in hastable, if no than add 1 in table                    1,0                    

check 10-3 = 7 is in a hashtable if no then add 3 in table               3,1

check 10-6 = 4 is in the hash table if no then add 6 in table           6,2

check 10-8 = 2 is in the hash table if no then add 8 in table           8,3

check 10-2 = 8 is in the hashtable, if yes then return i and value of key 8 from a table.

i.e index of 2 is 4 and  index of 8 is 3 so return [3,4]

Remember: If there are any duplicate numbers than do not add in the hash table as it will not support.
*If the problem would have been to find only pairs, not their position than we could have used the only hash set instead of the hash table.

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

Implementation :

public int[] TwoSum(int[] nums, int target)
        {
            int[] result = new int[2]{-1, -1};
            var map = new Dictionary<int, int>();
            for (int i = 0; i < nums.Count(); i++)
            {
                if (map.ContainsKey(target - nums[i]))
                {
                    result[1] = i;
                    result[0] = map[(target - nums[i])];
                    return result;
                }
                if(!map.ContainsKey(nums[i])) // add only if its not present
                map.Add(nums[i], i);
            }
           return result;
        }