ADD ONE TO THE NUMBER

Concepts Used

Linked list reversal

Difficulty Level

Medium.

Problem Statement :

You are given a linked list representing a number such that each individual node acts as a digit of the number.

Example:

The list 
HEAD->1->2->3->NULL corresponds to the number 123. You to add 1 to this number to get 124 i.e. 1->2->4.

See original problem statement here


EXPLANATION:

Approach 1(Reverse the linked list):

Reverse given linked list using Master algorithms online.. For example, 1-> 9-> 9 -> 9 is converted to 9-> 9 -> 9 ->1.For this changed linked list now traverse the list, in the left-most node add one. if this node’s value is equal to 9 then propagate a carry to the next Node. Do the same procedure until the carry is there.
Reverse the string back as in original form and then returned the head to get the string printed.

 struct Node 
    { 
    int data; 
    Node* next; 
    }; 

     Node *newNode(int data) 
    { 
    Node *new_node = new Node; 
    new_node->data = data; 
    new_node->next = NULL; 
    return new_node; 
    } 
    Node *reverse(Node *head) 
    { 
    Node * prev   = NULL; 
    Node * current = head; 
    Node * next; 
    while (current != NULL) 
    { 
        next  = current->next; 
        current->next = prev; 
        prev = current; 
        current = next; 
    } 
    return prev; 
    } 

    Node *addOneUtil(Node *head) 
    { 
    Node* res = head; 
    Node *temp, *prev = NULL; 

    int carry = 1, sum; 

    while (head != NULL) {
        sum = carry + head->data; 
        carry = (sum >= 10)? 1 : 0; 
        sum = sum % 10; 
        head->data = sum; 

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

    return res; 
    } 

    Node* addOne(Node *head) 
    { 
    head = reverse(head); 
    head = addOneUtil(head); 
    return reverse(head); 
     } 
     void printList(Node *node) 
    { 
    while (node != NULL) 
    { 
        printf("%d", node->data); 
        node = node->next; 
    } 
    printf("\n"); 
    } 
    int main(void) 
    { int t;scanf("%d",&t);
     while(t--)
    {
      char s[100000];
    scanf("%s",s);
    int x=s[0]-'0';
    Node* head1=newNode(x);
    Node* head=head1;
    for(int i=1;i<strlen(s);i++)
    {
      head1->next=newNode(s[i]-'0');
      head1=head1->next;
    }
    head = addOne(head); 

    printList(head); }

    return 0; 
    } 
 #include <bits/stdc++.h>
     using namespace std;
     struct Node 
    { 
    int data; 
    Node* next; 
    }; 

    Node *newNode(int data) 
    { 
    Node *new_node = new Node; 
    new_node->data = data; 
    new_node->next = NULL; 
    return new_node; 
    } 
    Node *reverse(Node *head) 
    { 
    Node * prev   = NULL; 
    Node * current = head; 
    Node * next; 
    while (current != NULL) 
    { 
        next  = current->next; 
        current->next = prev; 
        prev = current; 
        current = next; 
    } 
    return prev; 
     } 

    Node *addOneUtil(Node *head) 
      { 
    Node* res = head; 
    Node *temp, *prev = NULL; 

    int carry = 1, sum; 

    while (head != NULL){ 
        sum = carry + head->data; 
        carry = (sum >= 10)? 1 : 0; 
        sum = sum % 10; 
        head->data = sum; 

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

    return res; 
     } 

     Node* addOne(Node *head) 
    { 
    head = reverse(head); 
    head = addOneUtil(head); 
    return reverse(head); 
    } 
     void printList(Node *node) 
    { 
    while (node != NULL) 
    { 
        cout<<node->data; 
        node = node->next; 
    } 
    printf("\n"); 
     } 
       int main(void) 
    { int t;scanf("%d",&t);
    while(t--)
    {
      string s;
    cin>>s;
    int x=s[0]-'0';
    Node* head1=newNode(x);
    Node* head=head1;
    for(int i=1;i<s.length();i++)
    {
      head1->next=newNode(s[i]-'0');
      head1=head1->next;
    }
    head = addOne(head); 

    printList(head); }

    return 0; 
    } 
 class prepbytes 
    { 
static class Node  
{  
    int data;  
    Node next;  
} 
static Node newNode(int data)  
{  
    Node new_node = new Node();  
    new_node.data = data;  
    new_node.next = null;  
    return new_node;  
}
static Node reverse(Node head)  
{  
    Node prev = null;  
    Node current = head;  
    Node next = null;  
    while (current != null)  
    {  
        next = current.next;  
        current.next = prev;  
        prev = current;  
        current = next;  
    }  
    return prev;  
}  
static Node addOneUtil(Node head)  
{  
    Node res = head;  
    Node temp = null, prev = null;  
    int carry = 1, sum;  
    while (head != null)
    {
        sum = carry + head.data;  
        carry = (sum >= 10)? 1 : 0;  
        sum = sum % 10;  
        head.data = sum;  
        temp = head;  
        head = head.next;  
    }  
    if (carry > 0)  
        temp.next = newNode(carry);  
    return res;  
} 
static Node addOne(Node head)  
{ 
    head = reverse(head);  
    head = addOneUtil(head);  
    return reverse(head);  
} 
static void printList(Node node)  
{  
    while (node != null)  
    {  
        System.out.print(node.data);  
        node = node.next;  
    }  
    System.out.println();  
}  
//main 
}  

Approach 2(Recursive):

Recursively reach the last node and forward carry to previous nodes. Recursive solution doesn’t require reversing of linked list.

#include <bits/stdc++.h>
    using namespace std;
    struct node{
    int data;
    node* next;
     };
    node* newnode(int x)
    {
     node* temp=new node();
     temp->data=x;
     temp->next=NULL;
     return temp;
    }
     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;
     }
     int main()
    {
     int t;cin>>t;
     while(t--)
    {
    string s;
    cin>>s;
    int x=s[0]-'0';
    node* head1=newnode(x);
    node* head=head1;
    for(int i=1;i<s.length();i++)
    {
      head1->next=newnode(s[i]-'0');
      head1=head1->next;
    }
     node* headnew=reverse(head);
    int carry=1,sum=0;node* prev,*head2=headnew;
    while(headnew!=NULL)
    {
    sum=headnew->data+carry;
    carry=sum/10;
    headnew->data=sum%10;
    //cout<<sum%10<<" ";
    prev=headnew;
    headnew=headnew->next;
    }
     if(carry)
    {
    prev->next=newnode(carry);
    prev=prev->next;
    }
     node* headnew2=reverse(head2);
     while(headnew2!=NULL)
    {
    cout<<headnew2->data;
    headnew2=headnew2->next;
    }
     cout<<"\n";}
     return 0;
    }
class prepbytes { 
    static class Node 
    { 
        int data; 
        Node next; 
    } 
    static Node newNode(int data)  
    { 
        Node new_node = new Node(); 
        new_node.data = data; 
        new_node.next = null; 
        return new_node; 
    } 
    static int addWithCarry(Node head) 
    { 
        if (head == null) 
            return 1; 
        int res = head.data + addWithCarry(head.next); 
        head.data = (res) % 10; 
        return (res) / 10; 
    }  
    static Node addOne(Node head) 
    { 
        int carry = addWithCarry(head); 
        if (carry > 0) 
        { 
            Node newNode = newNode(carry); 
            newNode.next = head; 
            return newNode;  
        } 

        return head; 
    } 
    static void printList(Node node) 
    { 
        while (node != null) 
        { 
            System.out.print(node.data); 
            node = node.next; 
        } 
        System.out.println(); 
    } 
    //main
      }

Previous post List Reduction
Next post Min Query

Leave a Reply

Your email address will not be published. Required fields are marked *