İki rəqəm əlavə edin

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma Bloomberg Kupanq DocuSign Facebook google microsoft Über VMware Walmart Laboratoriyaları Yahoo
Bağlı siyahı RiyaziyyatBaxılıb 35

İki rəqəm əlavə edin ikisini boş olmayan verdiyimiz bir problemdir əlaqəli siyahı mənfi olmayan tam ədədi təmsil edir. Rəqəm tərs qaydada saxlanılır və hər qovşaqda yalnız bir rəqəm olmalıdır. İki ədədi əlavə edin və əlaqəli siyahıdan istifadə edərək nəticəni çap edin.

Giriş Formatı

İki tam dəyər N1 və N2 olan birinci sətir. Birinci nömrənin N1 rəqəmlərini ehtiva edən ikinci sətir. Nömrənin N2 rəqəmini ehtiva edən üçüncü sətir.

Çıxış formatı

Nəticəni əlaqəli siyahıdan istifadə edərək çap edin.

Məhdudiyyətlər

  • 0 <= düyün dəyəri <= 9.
Example Input-1:
3 3
5 2 1
2 8 5
Example Output-1:
7 0 7

İki rəqəm əlavə etmək üçün izah

Birinci rəqəm 125, ikinci nömrə 582-dir. Onları əlavə etdikdə 707-yə sahib olduq. Son cavabımız 707-dir. Daha yaxşı başa düşmək üçün aşağıdakı şəkillərə baxın:

Addım 1 Verilən giriş formatına uyğun olaraq əlaqəli siyahıları yaradın. Bağlı bir siyahıda rəqəmləri tərs qaydada əlavə edin.

İki rəqəm əlavə edinPin

Addım 2  Hər əlaqəli siyahıda birdən bir rəqəmdən sağdan sola keçin. Sağdan sola keçmək üçün bu əlaqəli siyahıları geri düzəldirik. Hər iki əlaqəli siyahının qovşaqlarının məlumatlarını əlavə edin və başqa bir əlaqəli siyahıda saxlayın. Əlavə arasında hər hansı bir daşınma baş verərsə, onu növbəti qovşaqda istifadə edin.

İki rəqəm əlavə edinPin

Addım 3 Başları bir-bir hərəkət etdirin və nəticələnmiş siyahıya dəyəri əlavə edin.

Pin

Addım 4 Başları bir-bir hərəkət etdirin və nəticələnmiş siyahıya dəyəri əlavə edin.

Pin

Addım 5 İndi nəticə çıxarılan 7-> 0-> 7 siyahısının dəyərlərini çap edirik.

İki ədədi əlavə etmək üçün alqoritm

Algorithm:
Step:1 If h1 is the head of first linked list and h2 is the head of second linked list then:
       while(h1!=NULL and h2!=NULL) then:
       1.1) add the data of both nodes and add to a final resultant linked list.
Step:2 while(h1!=NULL) then:
       add the nodes of linked list 1 to the resultant linked list.
Step:3 while(h2!=NULL) then:
       add the nodes of linked list 2 to the resultant linked list.  
Step:4 Print the final resultant linked list.

Üçün iki tətbiq əlavə edin

/*C++ Implementation of Add two numbers problem*/ 
#include<bits/stdc++.h>
using namespace std;
/*structure of node of linked list which contain data and a pointer which is point to the next node*/
struct ListNode 
{
    /*value of node*/
    int val;
    /*pointer to the next node*/
    ListNode *next;
};
/*Create a node with given data*/
ListNode *newnode(int data)
{
    ListNode *temp= new ListNode();
    temp->val=data;
    temp->next=NULL;
    return temp;
}
void create_linked_list(ListNode** head, int data)  
{  
    /*allocate node*/
    ListNode* temp = newnode(data);  
    /*link the old list off the new node*/
    temp->next=(*head);  
    /* move the head to point to the new node*/
    (*head)=temp;  
}
void print_linked_list(ListNode* head)
{
    while(head!=NULL)
    {
        cout<<head->val<<" ";
        head=head->next;
    }
}
/*add two linked list*/
ListNode* add_two_numbers(ListNode* l1, ListNode* l2)
{
    int carry=0;
    ListNode* res;
    ListNode **ans=&res;
    /*if both linked list have nodes*/
    while(l1!=NULL&&l2!=NULL)
    {
        (*ans)= newnode((l1->val+l2->val+carry)%10);
        carry=(l1->val+l2->val+carry)/10;
        ans=&((*ans)->next);
        l1=l1->next;
        l2=l2->next;
    }
    /*if linked list 1 have nodes*/
    while(l1!=NULL)
    {
        (*ans)= newnode((l1->val+carry)%10);
        carry=(l1->val+carry)/10;
        ans=&((*ans)->next); 
        l1=l1->next;
    }
    /*if linked list 2 have nodes*/
    while(l2!=NULL)
    {
        (*ans)= newnode((l2->val+carry)%10);
        carry=(l2->val+carry)/10;
        ans=&((*ans)->next); 
        l2=l2->next;
    }
    /*if their is generate a carry then create one more node in linked list and store the carry.*/
    if(carry>0)
    {
        (*ans)= newnode(carry);
        carry/=10;
        ans=&((*ans)->next);
    }
    return res;
}
/*function use to reverse the linked list*/
ListNode* reverse_linked_list(ListNode* head)
{
    ListNode* current=head;
    ListNode* next=NULL;
    ListNode* prev=NULL;
    while(current!=NULL)
    {
        next=current->next;
        current->next=prev;
        prev=current;
        current=next;
    }
    return prev;
}
int main() 
{ 
    int n1,n2;
    /*take the input n1,n2*/
    cin>>n1>>n2;
    ListNode* result=NULL;
    ListNode* ll1=NULL;
    ListNode* ll2=NULL;
    /*take input linked list 1*/
    for(int i=0;i<n1;i++)
    {
        int x;
        cin>>x;
        create_linked_list(&ll1,x);
    }
    /*take input linked list 2*/
    for(int i=0;i<n2;i++)
    {
        int x;
        cin>>x;
        create_linked_list(&ll2,x);
    }
    /*print first linked list*/
    cout<<"First linked list is: ";
    print_linked_list(ll1);
    cout<<endl;
    /*print second linked list*/
    cout<<"Second linked list is: ";
    print_linked_list(ll2);
    cout<<endl;
    /*reverse linkel list 1*/
    ListNode* l1=reverse_linked_list(ll1);
    /*reverse linkel list 2*/
    ListNode* l2=reverse_linked_list(ll2);
    ListNode* ans= add_two_numbers(l1,l2);
    /*print reslutant linked list*/
    cout<<"Resultant linked list is: ";
    print_linked_list(ans);
    cout<<endl;
    return 0; 
}
3 2 
2 4 3
5 6
First linked list is: 3 4 2 
Second linked list is: 6 5 
Resultant linked list is: 7 0 4

Zamanın mürəkkəbliyi

O (N) burada N - n1, n2-nin maksimum dəyəri. Bağlı siyahıdan sadəcə keçirik xətti vaxt zaman mürəkkəbliyi də xətti olur.

Kosmik Mürəkkəblik

O (N) çünki başqa bir əlaqəli siyahı yaradırıq, burada N qovluğu ola bilər, burada N böyük ölçülü bağlı siyahıda rəqəmdir.

References

Translate »