PLEASE READ CAREFULLY! Write a program that allows the user to enter two positiv

Question

PLEASE READ CAREFULLY!

Write a program that allows the user to enter two positive integers and outputs their sum. Sounds simple? Here's the catch: The numbers may be any size! They may be way too large to store in a single variable. You may not assume any particular maximum number of digits.

Hint: 1. Use linked list to store the huge number.

2. Store the 2 numbers in two linked list in backward order.

3. Compute sum from the beginning of the two list.

4. Store the sum in a new linked list in forward order.

5. Print the sum list in forward order.

Write a program that allows the user to enter two positive integers and outputs their sum. Sounds simple? Here's the catch: The numbers may be any size! They may be way too large to store in a single variable. You may not assume any particular maximum number of digits.

Here are two sample runs:

Enter first positive integer: 87435704325782438757285045089847

Enter second positive integer: 4523852345234255895

Sum = 87435704325786962609630279345742

Enter first positive integer: 99999999999999999999999999999999999999999 99999999999999999999999999999999999999999999999999999999999999999999999 99999999999999999999999999999999999999999999999

Enter second positive integer: 1

Sum = 10000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000

Explanation / Answer

#include<stdio.h>
#include<conio.h>

#include<stdlib.h>

struct node   // Linked list node
{
   int data;
   struct node* next;
};

struct node *newNode(int data) // Function to create a new node with giving the data
{
   struct node *new_node = (struct node *) malloc(sizeof(struct node));
   new_node->data = data;
   new_node->next = NULL;
   return new_node;
}

void push(struct node** head_ref, int new_data) // Function to insert a node at the beginning of the Doubly Linked List
{

   struct node* new_node = newNode(new_data); // allocate a node

   new_node->next = (*head_ref); // link the old list off to the new node

    (*head_ref) = new_node; // move the head to point to the new node
}

/* Adding the contents of two linked lists and return the head node of resultant list
struct node* addTwoLists (struct node* first, struct node* second)
{
   struct node* res = NULL; // res is head node of the resultant list
   struct node *temp, *prev = NULL;
   int carry = 0, sum;

   while (first != NULL || second != NULL) //while both the lists exists
   {
       // Calculate value of next digit in resultant list.
       // The next digit is sum of following things
       // (i) Carry
       // (ii) Next digit of first list (if there is a next digit)
       // (ii) Next digit of second list (if there is a next digit)
       sum = carry + (first? first->data: 0) + (second? second->data: 0);

       carry = (sum >= 10)? 1 : 0;  // update carry for next calulation

   sum = sum % 10;  // update sum if it is greater than 10

   temp = newNode(sum);   // Create a new node with sum as data

  
       if(res == NULL) // if this is the first node then set it as head of the resultant list
           res = temp;
       else // If this is not the first node then connect it to the rest.
           prev->next = temp;

    prev = temp;    // Set prev for next insertion

       if (first) first = first->next; // Move first pointers to next node
       if (second) second = second->next; //Move  second pointer to the next node
   }

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

    return res;     // return head of the resultant list
}

void printList(struct node *node) // function to print a linked list
{
   while(node != NULL)
   {
       printf("%d ", node->data);
       node = node->next;
   }
   printf(" ");
}

int main(void) // program to test above function
{
   struct node* res = NULL;
   struct node* first = NULL;
   struct node* second = NULL;

  printf("Enter first positive integer: ");

scanf("%d",&first);
   printList(first);

printf("Enter second positive integer: ");

scanf("%d",&second);
   printList(second);

   // Add the two lists and see result
   res = addTwoLists(first, second);
   printf("Resultant list is ");
   printList(res);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.