Advertisement
i_love_rao_khushboo

Untitled

Jan 23rd, 2023
1,198
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.25 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define ld long double
  6. #define ull unsigned long long
  7. #define pb push_back
  8. #define ppb pop_back
  9. #define pf push_front
  10. #define ppf pop_front
  11. #define mp make_pair
  12. #define F first
  13. #define S second
  14. #define PI 3.1415926535897932384626
  15. #define sz(x) ((int)(x).size())
  16. #define vset(v, n, val) v.clear(); v.resize(n, val)
  17.  
  18. typedef pair<int, int> pii;
  19. typedef pair<ll, ll> pll;
  20. typedef vector<int> vi;
  21. typedef vector<ll> vll;
  22. typedef vector<ull> vull;
  23. typedef vector<bool> vb;
  24. typedef vector<char> vc;
  25. typedef vector<string> vs;
  26. typedef vector<pii> vpii;
  27. typedef vector<pll> vpll;
  28. typedef vector<vi> vvi;
  29. typedef vector<vll> vvll;
  30. typedef vector<vull> vvull;
  31. typedef vector<vb> vvb;
  32. typedef vector<vc> vvc;
  33. typedef vector<vs> vvs;
  34.  
  35. /************************************************** DEBUGGER *******************************************************************************************************/
  36.  
  37. #ifndef ONLINE_JUDGE
  38. #define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
  39. #else
  40. #define debug(x)
  41. #endif
  42.  
  43. void _print(ll t) { cerr << t; }
  44. void _print(int t) { cerr << t; }
  45. void _print(string t) { cerr << t; }
  46. void _print(char t) { cerr << t; }
  47. void _print(ld t) { cerr << t; }
  48. void _print(double t) { cerr << t; }
  49. void _print(ull t) { cerr << t; }
  50.  
  51. template <class T, class V> void _print(pair <T, V> p);
  52. template <class T> void _print(vector <T> v);
  53. template <class T> void _print(vector <vector<T>> v);
  54. template <class T> void _print(set <T> v);
  55. template <class T, class V> void _print(map <T, V> v);
  56. template <class T> void _print(multiset <T> v);
  57. template <class T, class V> void _print(multimap <T, V> v);
  58. template <class T> void _print(queue <T> v);
  59. template <class T> void _print(priority_queue <T> v);
  60. template <class T> void _print(stack <T> s);
  61.  
  62. // modify it's definition below as per need such as it can be used for STL containers with custom args passed
  63. template <class T> void _print(T v);
  64.  
  65. template <class T, class V> void _print(pair <T, V> p) { cerr << "{"; _print(p.F); cerr << ","; _print(p.S); cerr << "}"; }
  66. template <class T> void _print(vector <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  67. template <class T> void _print(vector <vector<T>> v) { cerr << "==>" << endl; for (vector<T> vec : v) { for(T i : vec) {_print(i); cerr << " "; } cerr << endl; } }
  68. template <class T> void _print(set <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  69. template <class T, class V> void _print(map <T, V> v) { cerr << "[ "; for (auto i : v) {_print(i); cerr << " "; } cerr << "]"; }
  70. template <class T> void _print(multiset <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  71. template <class T, class V> void _print(multimap <T, V> v) { cerr << "[ "; for (auto i : v) {_print(i); cerr << " "; } cerr << "]"; }
  72. template <class T> void _print(queue <T> v) { cerr << "[ "; while(!v.empty()) {_print(v.front()); v.pop(); cerr << " "; } cerr << "]"; }
  73. template <class T> void _print(priority_queue <T> v) { cerr << "[ "; while(!v.empty()) {_print(v.top()); v.pop(); cerr << " "; } cerr << "]"; }
  74. template <class T> void _print(stack <T> v) { cerr << "[ "; while(!v.empty()) {_print(v.top()); v.pop(); cerr << " "; } cerr << "]"; }
  75. template <class T> void _print(T v) {  }
  76.  
  77. /*******************************************************************************************************************************************************************/
  78.  
  79. const int INF = 0x3f3f3f3f;
  80. const int mod = 1e9+7;
  81.  
  82. ll mod_exp(ll a, ll b) { a %= mod; if(a == 0) return 0LL; ll res = 1LL;
  83.                          while(b > 0) { if(b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; }
  84.                          
  85. ll mod_inv(ll a) { return mod_exp(a, mod - 2); } // works only for prime value of "mod"
  86. ll GCD(ll a, ll b) { return (b == 0) ? a : GCD(b, a % b); }
  87.  
  88. /******************************************************************************************************************************/
  89.  
  90. // Making a node class containing the value and a pointer
  91. // to next available node
  92. class ListNode {
  93.     public:
  94.         int val;
  95.         ListNode *next;
  96. };
  97.  
  98. class LinkedList {
  99.     public:
  100.         // head and tail pointers
  101.         ListNode *head, *tail;
  102.        
  103.         // default constructor. Initializing head and tail pointers
  104.         LinkedList() {
  105.             head = NULL;
  106.             tail = NULL;
  107.         }
  108.        
  109.         // inserting elements (at the end of the list)
  110.         void insert(int data) {
  111.             // make a new node
  112.             ListNode *new_node = new ListNode;
  113.             new_node->val = data;
  114.             new_node->next = NULL;
  115.            
  116.             // If list is empty, make the new node, the head
  117.             // initialise tail also as new node
  118.             if(head == NULL) {
  119.                 head = new_node;
  120.                 tail = new_node;
  121.             }
  122.            
  123.             else {
  124.                 tail->next = new_node;
  125.                 tail = tail->next;
  126.             }
  127.         }
  128.        
  129.         void display() {
  130.             ListNode *tmp = head;
  131.             while(tmp != NULL) {
  132.                 cout << tmp->val;
  133.                 tmp = tmp->next;
  134.                 if(tmp != NULL) cout << "->";
  135.             }
  136.            
  137.             cout << "\n";
  138.         }      
  139. };
  140.  
  141. ListNode* reverse(ListNode *head) {
  142.     ListNode *prv = NULL, *cur = head, *nxt = head;
  143.     while(nxt != NULL) {
  144.         nxt = nxt->next;
  145.         cur->next = prv;
  146.         prv = cur;
  147.         cur = nxt;
  148.     }
  149.    
  150.     return prv;
  151. }
  152.  
  153. ListNode* add_2_numbers(ListNode *h1, ListNode *h2) {
  154.     ListNode *tmp_head = new ListNode;
  155.     tmp_head->val = -1;
  156.     tmp_head->next = NULL;
  157.    
  158.     ListNode *tmp = tmp_head;
  159.     int carry = 0;
  160.     int nodes = 0;
  161.    
  162.     while(h1 or h2 or carry) {
  163.         int num = 0;
  164.         if(h1) num += h1->val;
  165.         if(h2) num += h2->val;
  166.         if(carry) num += carry;
  167.        
  168.         if(h1) {
  169.             h1->val = num % 10;
  170.             tmp->next = h1;
  171.         }
  172.        
  173.         else if(h2) {
  174.             h2->val = num % 10;
  175.             tmp->next = h2;
  176.         }
  177.        
  178.         else {
  179.             ListNode *new_node = new ListNode;
  180.             new_node->val = num % 10;
  181.             new_node->next = NULL;
  182.             tmp->next = new_node;
  183.         }
  184.        
  185.         tmp = tmp->next;
  186.  
  187.         nodes += 1;
  188.        
  189.         carry = (num / 10);
  190.        
  191.         if(h1) h1 = h1->next;
  192.         if(h2) h2 = h2->next;
  193.     }
  194.    
  195.     tmp = reverse(tmp_head->next);
  196.     if(nodes > 1) while(tmp and tmp->val == 0) tmp = tmp->next;
  197.     tmp = reverse(tmp);
  198.    
  199.     return tmp;
  200. }
  201.  
  202. void solve()
  203. {
  204.     int n, m; cin >> n >> m;
  205.     LinkedList l1, l2;
  206.    
  207.     for(int i = 0; i < n; i++) {
  208.         int x; cin >> x;
  209.         l1.insert(x);
  210.     }
  211.    
  212.     for(int i = 0; i < m; i++) {
  213.         int x; cin >> x;
  214.         l2.insert(x);
  215.     }
  216.    
  217.     l1.display();
  218.     l2.display();
  219.    
  220.     ListNode *tmp = add_2_numbers(l1.head, l2.head);
  221.     while(tmp != NULL) {
  222.         cout << tmp->val;
  223.         tmp = tmp->next;
  224.         if(tmp != NULL) cout << "->";
  225.     }
  226.            
  227.     cout << "\n";
  228. }
  229.  
  230. int main()
  231. {
  232.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  233.  
  234.     // #ifndef ONLINE_JUDGE
  235.     //     freopen("input.txt", "r", stdin);
  236.     //     freopen("output.txt", "w", stdout);
  237.     // #endif
  238.    
  239.     // #ifndef ONLINE_JUDGE
  240.     //      freopen("error.txt", "w", stderr);
  241.     // #endif
  242.    
  243.     int t = 1;
  244.     // int test = 1;
  245.     // cin >> t;
  246.     while(t--) {
  247.         // cout << "Case #" << test++ << ": ";
  248.         solve();
  249.     }
  250.  
  251.     return 0;
  252. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement