Advertisement
H-a-y-K

Untitled

Jan 26th, 2021
321
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.28 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. bool is_zero(int arr[], int size)
  4. {
  5.     for (int i = 0; i < size; i++)
  6.         if (arr[i] != 0)
  7.             return false;
  8.     return true;
  9. }
  10.  
  11. int truncate(int arr[], int size, int result[] = nullptr)
  12. {
  13.     int zero_count = 0;
  14.  
  15.     if (!is_zero(arr, size))
  16.     {
  17.         for (int i = 0; i < size; i++)
  18.         {
  19.             if (arr[i] == 0)
  20.                 zero_count++;
  21.             else
  22.             {
  23.                 break;
  24.             }
  25.         }
  26.     }
  27.  
  28.     if (result != nullptr)
  29.     {
  30.         for (int i = 0; i < size - zero_count; i++)
  31.             result[i] = arr[i + zero_count];
  32.  
  33.         for (int i = size - zero_count; i < size; i++)
  34.             result[i] = -1;
  35.     }
  36.  
  37.     return size - zero_count;
  38. }
  39.  
  40. bool smaller_than(int n[], int m[], int size1, int size2)
  41. {
  42.     int trun_n[size1], trun_m[size2];
  43.  
  44.     int trun_size1 = truncate(n, size1, trun_n);
  45.     int trun_size2 = truncate(m, size2, trun_m);
  46.  
  47.     if (trun_size1 < trun_size2)
  48.         return true;
  49.  
  50.     if (trun_size1 > trun_size2)
  51.         return false;
  52.  
  53.     for (int i = 0; i < trun_size1; i++)
  54.     {
  55.         if (trun_n[i] < trun_m[i])
  56.             return true;
  57.     }
  58.  
  59.     return false;
  60. }
  61.  
  62. inline bool bigger_than(int n[], int m[], int size1, int size2)
  63. {
  64.     return smaller_than(m, n, size2, size1);
  65. }
  66.  
  67. bool equal(int n[], int m[], int size1, int size2)
  68. {
  69.     if (size1 != size2)
  70.         return false;
  71.     else
  72.     {
  73.         for (int i = 0; i < size1; i++)
  74.         {
  75.             if (n[i] != m[i])
  76.                 return false;
  77.         }
  78.     }
  79.  
  80.     return true;
  81. }
  82.  
  83. int* subtract(int n[], int m[], int result[], int size1, int size2)
  84. {
  85.     int n_reverse[size1];
  86.     int m_reverse[size2];
  87.  
  88.     for (int i = size1 - 1; i >= 0; i--)
  89.     {
  90.         n_reverse[size1 - i - 1] = n[i];
  91.     }
  92.  
  93.     for (int i = size2 - 1; i >= 0; i--)
  94.     {
  95.         m_reverse[size2 - i - 1] = m[i];
  96.     }
  97.  
  98.     int *first;
  99.     int *second;
  100.  
  101.     if (smaller_than(n, m, size1, size2))
  102.     {
  103.         first = m_reverse;
  104.         second = n_reverse;
  105.     }
  106.     else
  107.     {
  108.         first = n_reverse;
  109.         second = m_reverse;
  110.     }
  111.  
  112.     int max_size = std::max(size1, size2);
  113.     int min_size = std::min(size1, size2);
  114.  
  115.     int carry = 0;
  116.  
  117.     int sub;
  118.  
  119.     for (int i = 0; i < max_size; i++)
  120.     {
  121.         if (i < min_size)
  122.         {
  123.             sub = first[i] - second[i] - carry;
  124.  
  125.             if (sub < 0)
  126.             {
  127.                 sub = sub + 10;
  128.                 carry = 1;
  129.             }
  130.             else
  131.             {
  132.                 carry = 0;
  133.             }
  134.  
  135.             result[max_size - i - 1] = sub;
  136.         }
  137.         else
  138.         {
  139.             if (carry == 1)
  140.             {
  141.                 result[max_size - i - 1] = first[i] - carry;
  142.                 carry = 0;
  143.             }
  144.             else
  145.                 result[max_size - i - 1] = first[i];
  146.         }
  147.     }
  148.  
  149.     return result;
  150. }
  151.  
  152. int* remainder(int n[], int m[], int result[], int size1, int size2)
  153. {
  154.     if (!is_zero(m, size2))
  155.     {
  156.         if (is_zero(n, size1) || equal(n, m, size1, size2))
  157.         {
  158.             for (int i = 0; i < std::max(size1, size2); i++)
  159.                 result[i] = 0;
  160.         }
  161.         else if (smaller_than(n, m, size1, size2))
  162.         {
  163.             for (int i = 0; i < size1; i++)
  164.                 result[i] = n[i];
  165.         }
  166.         else
  167.         {
  168.             for (int i = 0; i < std::max(size1, size2); i++)
  169.                 result[i] = n[i];
  170.             // assume m > 0
  171.             while (bigger_than(result, m, size1, size2))
  172.             {
  173.                 subtract(result, m, result, size1, size2);
  174.             }
  175.            
  176.         }
  177.     }
  178.  
  179.     return result;
  180. }
  181.  
  182. int main() {
  183.     int n[100];
  184.     int m[100];
  185.     int size1, size2;
  186.  
  187.     for (int i = 0; i < 100; i++)
  188.     {
  189.         std::cin >> n[i];
  190.         if (n[i] == -1)
  191.         {
  192.             size1 = i;
  193.             break;
  194.         }
  195.     }
  196.  
  197.     for (int i = 0; i < 100; i++)
  198.     {
  199.         std::cin >> m[i];
  200.         if (m[i] == -1)
  201.         {
  202.             size2 = i;
  203.             break;
  204.         }
  205.     }
  206.  
  207.     int result[std::max(size1, size2)];
  208.  
  209.     remainder(n, m, result, size1, size2);
  210.  
  211.     for (int i = 0; i < std::max(size1, size2); i++)
  212.         std::cout << result[i];
  213. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement