DEV Community: Kamal Sharma

Add Two Numbers Represented by Linked Lists

Kamal Sharma — Wed, 22 Dec 2021 07:55:43 +0000

Problem Statement

Given 2 numbers, where each digit is represented by nodes of a LinkedList, find the sum of the 2 numbers represented as LinkedList.

Sample Test Cases

Input 1:
firstList = 7 5 9 4 6
secondList = 8 4

Output 1: result = 5 0 0 5

Adding the linked lists in the above manner with the rules of sum and carry of addition, we get the resultant linked-list as 5 -> 0 -> 0 -> 5 -> 6.

Input 2:
firstList = 0
secondList = 0
Output 2:
result = 0

Explanation 2:
Both the linked lists in the above example represent the number 0, so the result is also a single node with the value 0.

Approach
We approach this problem as follows. We will perform a traversal on both the lists and append zeros on the list which has a lesser number of digits till both numbers have an equal number of digits. Then we can recursively start from the start nodes of both the lists, where the function recursively moves ahead on both the lists till we reach the end. In the process of recursion, we will keep creating new nodes which will store the sum of the digits, and the recursive function returns the carry onto the next node for the sum operation.
The algorithm is as described below:

Perform a traversal on both the linked lists and make the shorter list of length equal to the long list by appending zeros to its end.

Start a recursive function from the start nodes of both the lists, where the function will further call the next nodes of the list.
The recursion continues till we reach the end of a linked list.
While continuing our recursion, we will keep adding new nodes which will store the sum of digits of our result, and the recursive function will return the carry to the next step in each recursive call.
Run the code with InterviewBit's Online C++ Compiler

C++ Code

// class Node {
// public:
//     int data;
//     Node* next;
// };
Node * addTwoLists(Node * first, Node * second) {
  Node * res = NULL;
  Node * temp;
  Node * prev = NULL;
  int carry = 0, sum = 0;
  while (first != NULL || second != NULL) {
    sum = carry;
    sum += first != NULL ? first -> data : 0;
    sum += second != NULL ? second -> data : 0;
    if (sum >= 10) {
      carry = 1;
    } else {
      carry = 0;
    }
    sum %= 10;
    temp = newNode(sum);
    if (res != NULL) {
      prev -> next = temp;
    } else {
      res = temp;
    }
    prev = temp;
    if (first) {
      first = first -> next;
    }
    if (second) {
      second = second -> next;
    }
  }

  if (carry > 0)
    temp -> next = newNode(carry);
  return res;
}

Node * reverse(Node * head) {
  if (head == NULL || head -> next == NULL) {
    return head;
  }
  Node * rest = reverse(head -> next);
  head -> next -> next = head;
  head -> next = NULL;
  return rest;
}

Node * solve(Node * list1, Node * list2) {
  list1 = reverse(list1);
  list2 = reverse(list2);
  Node * added = addTwoLists(list1, list2);
  return added;
}

Java Code

/*
static class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}
*/
public static Node addTwoLists(Node first, Node second) {
  Node start1 = new Node(0);
  start1.next = first;
  Node start2 = new Node(0);
  start2.next = second;
  addPrecedingZeros(start1, start2);
  Node result = new Node(0);
  if (sumTwoNodes(start1.next, start2.next, result) == 1) {
    Node dummy = new Node(1);
    dummy.next = result.next;
    result.next = dummy;
  }
  return result.next;
}
public static int sumTwoNodes(Node first, Node second, Node result) {
  if (first == null) {
    return 0;
  }
  int sum = 0;
  sum += first.data;
  sum += second.data;
  sum += sumTwoNodes(first.next, second.next, result);
  Node dummy = new Node(sum % 10);
  dummy.next = result.next;
  result.next = dummy;
  return sum / 10;
}
public static void addPrecedingZeros(Node start1, Node start2) {
  Node next1 = start1.next;
  Node next2 = start2.next;
  while (next1 != null && next2 != null) {
    next1 = next1.next;
    next2 = next2.next;
  }
  if (next1 == null) {
    if (next2 != null) {
      while (next2 != null) {
        Node dummy = new Node(0);
        dummy.next = start1.next;
        start1.nedummy dummy;
        next2 = next2.next;
      }
    }
  } else if (next2 == null) {
    if (next1 != null) {
      while (next1 != null) {
        Node dummy = new Node(0);
        dummy.next = start2.next;
        start2.next = dummy;
        next1 = next1.next;
      }
    }
  }
}
public static Node solve(Node first, Node second) {
  Node result = addTwoLists(first, second);
  return result;
}

Reference - InterviewBit

C++ and Java Code for Sieve of Eratosthenes

Kamal Sharma — Fri, 01 Oct 2021 06:59:40 +0000

The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million or so. Following is the algorithm to find all the prime numbers less than or equal to a given integer n by the Eratosthenes method:

When the algorithm terminates, all the numbers in the list that are not marked are prime.

Firstly write all the numbers from 2,3,4…. n
Now take the first prime number and mark all its multiples as visited.
Now when you move forward take another number which is unvisited yet and then follow the same step-2 with that number.
All numbers in the list left unmarked when the algorithm ends are referred to as prime numbers.

C++ Implementation

void SieveOfEratosthenes(int n)
{
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));

    for (int p = 2; p * p <= n; p++)
    {
        if (prime[p] == true)
        {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
    for (int p = 2; p <= n; p++)
        if (prime[p])
            cout << p << " ";
}

Java Implementation

class SieveOfEratosthenes {
    void sieveOfEratosthenes(int n)
    {
        boolean prime[] = new boolean[n + 1];
        for (int i = 0; i <= n; i++)
            prime[i] = true;

        for (int p = 2; p * p <= n; p++){
            if (prime[p] == true)
            {
                for (int i = p * p; i <= n; i += p)
                    prime[i] = false;
            }
        }

        for (int i = 2; i <= n; i++)
        {
            if (prime[i] == true)
                System.out.print(i + " ");
        }
    }
}

Time complexity of Sieve of Eratosthenes :
o(n * (log(log(n)))).

Space complexity: O(1)
Source - InterviewBit

HTML vs XML

Kamal Sharma — Thu, 25 Feb 2021 15:26:17 +0000

HTML and XML are platform-independent markup languages. They are both based on SGML - Standard Generalized Markup Language. HTML was designed to facilitate transferring of web-based documents.

XML was later developed to provide interoperability with HTML and simplify its implementation. HTML focuses on describing the web page structure and displaying information. Whereas, XML focuses on storing and transferring this information.

If you are preparing for the HTML interview, you could maybe check the InterviewBit guide on HTML to clear the interview

HTML

HTML or Hypertext Markup Language is popularly used to create web pages and web applications. It is the basis for all web pages. It describes web page structure It is a markup language and consists of various HTML elements composed of tags and their content. It is a hypertext language that creates a chain of links of documents. Standard HTML pages are static. HTML5.2 is the latest version of HTML.

HTML is easy to learn and use because of its simple syntax. It is supported by all browsers and is free, lightweight, and user-friendly.

However, HTML cannot be used to create dynamic pages. Also, HTML is not centralized - all web pages need to be programmed separately.

Let’s see a simple example for an HTML program

<!DOCTYPE HTML>
<html lang="en">
<meta charset="UTF-8">
<HTML>
<head>
<title>Welcome to the world</title>
</head>
<body>
<h1>Web Development</h1>
<p>HTML vs XML</p>
</body>
</html>

XML

XML or eXtensible Markup Language’ is also used to create web pages and web applications. It is a textual data format with strong support via Unicode for several different human languages. Its design goals focus on simplicity, generality, and usability across the internet. It is dynamic. XML1.1 is the latest version of XML.

It makes documents transportable across systems and applications and simplifies platform change and data sharing processes. It is extendable, easy to read and understand, and does not affect data presentation.

XML is redundant and verbose compared to other text-based formats. Large data volumes can lead to high storage and transportation cost due to redundancy in XML syntax.

Let’s now see an example for XML program:

<?xml version = "1.0"?>
<InterviewBit>
    <address category = "Practice">
            <track>Web Development</track>
            <Display>HTML</Display>
            <transport>XML</transport>
    </address>
</development>

Difference between HTML and XML

The following table summarizes some of the key differences between HTML and XML.

HTML	XML
HTML stands for Hypertext Markup Language	XML stands for eXtensible Markup Language
It is a predefined markup language.	It is a standard markup language that provides a framework to define other markup languages.
It is used for encoding web pages and to display data.	XML is used to transport and store data.
It focuses on how data will look on the client-side.	It focuses on what the data represents and describes.
It is static as it is used to display data.	It is dynamic as it is used to carry information.
It offers native support.	In XML, objects are expressed by conventions with the help of elements and attributes.
It has predefined tags.	It supports user-defined tags.
It has a limited number of tags	XML tags are extensible.
In HTML, it is not mandatory to use a closing tag.	In XML, it is mandatory to use a closing tag.
HTML can ignore small errors	XML does not allow errors.
It is case insensitive.	It is case-sensitive.
It does not preserve whitespaces.	It preserves whitespaces.
HTML parsers in most web browsers accept element overlapping.	In XML, elements can not overlap
HTML parsers in most web browsers accept element overlapping.	In XML, elements can not overlap
It natively recognizes the null value	Xsi:nil on elements is required in an XML instance document to indicate a null value.
In HTML, extra application code is not needed to parse text.	XML DOM application and implementation code are required for mapping text back into JavaScript objects.