2

The following code is giving an error by saying the message "singed integer overflow". And the error is in this test case :

input : 208170109961052

Output : 4611790103482368430

Expected Output : 104085054980526

The input range is 1 ≤ n ≤ 10^15

#include "bits/stdc++.h"
using namespace std;

int main()
{
    long long n;
    cin >> n;
    if (n % 2)
    {
        cout << (((n - 1) * (n - 1)) / 4 + (n - 1) / 2) - (((n + 1) / 2) * ((n + 1) / 2)) << '\n';
    }
    else
    {
        cout << ((n * n) / 4 + n / 2) - ((n / 2) * (n / 2)) << '\n';
    }

    return 0;
}

As far as I know long long is the largest datatype. How can I solve this ?

Nazmus Sakib Sibly
  • 55
  • 6
  • Does this answer your question? [What type to use for integers larger than 2^32 in C++?](https://stackoverflow.com/questions/934358/what-type-to-use-for-integers-larger-than-232-in-c) – Raymond Chen Jun 25 '22 at 04:24
  • 13
    I suspect that your teacher or whoever assigned this wants you to use algebra to simplify the expression so that overflow *doesn't* happen, rather than just throwing larger data types at the problem. A lesson in algorithm design, no doubt. – Silvio Mayolo Jun 25 '22 at 04:24
  • This code was to calculate the sum of f(n) = - 1 + 2 - 3 + 4 - 5 + ... ... where n is the final term to calculate the sum. What I have done is I calculated the Summation of Even and Odd numbers separately using this formula. Because the runtime for this code was 1s. – Nazmus Sakib Sibly Jun 25 '22 at 04:30
  • But it too ended up an error. – Nazmus Sakib Sibly Jun 25 '22 at 04:30
  • 4
    @nazmussakibsibly … what do `-1 + 2`, and `-3 + 4` and `-5 + 6` have in common … ? – donkopotamus Jun 25 '22 at 04:33
  • I should have thought out of the box. Thanks – Nazmus Sakib Sibly Jun 25 '22 at 04:41
  • 2
    You don't even have to think outside the box. Just simplify the terms. For example: `(n * n) / 4 == (n / 2) * (n / 2)`. If you just rearange your formular and remove the terms that cancel each other what you will be left with should fit the type. – Goswin von Brederlow Jun 25 '22 at 06:28
  • 6
    [Why should I not `#include `?](https://stackoverflow.com/q/31816095/1458097) And also: [Why is `using namespace std;` considered bad practice?](https://stackoverflow.com/q/1452721/1458097) – heap underrun Jun 25 '22 at 06:44
  • BTW: You can estimate the number of bits needed for representing a number by noting `10^3 = 1000 ≈ 1024 = 2^10`. So for `10^30` you need about `30/3*10 = 100` bits + `1` sign bit. – Sebastian Jun 25 '22 at 07:20
  • For other purposes consider using arbitrary precision arithmetic like in [GMPlib](https://gmplib.org/). In your question you don't need it – Basile Starynkevitch Jun 25 '22 at 07:43
  • 1
    **singed** integer overflow is caused by overheating the CPU and the bits get scorched and blistered. – Eljay Jun 25 '22 at 11:30

1 Answers1

4

The solution will be to simplify your terms:

Term 1:

(((n - 1) * (n - 1)) / 4 + (n - 1) / 2) - (((n + 1) / 2) * ((n + 1) / 2)) 

n^2 - 2n + 1      n - 1            n+1      n+1 
------------  +  ------   -   (   ----- *  ----- )
      4             2               2        2


n^2 - 2n + 1      n - 1            (n+1)   *  (n+1) 
------------  +  ------   -   (   ---------------- )
      4             2                   4

n^2 - 2n + 1      2n - 2              n^2 + 2n -1 
------------  +  --------   -   (   ---------------- )
      4             4                      4
      
      
n^2 - 2n + 1  +    2n - 2    - ( n^2 + 2n -1 )
------------------------------------------------ 
                      4                      
                      
n^2 - 2n + 1  +    2n - 2    -n^2 - 2n + 1 
------------------------------------------------ 
                      4                      
                      
    -2n  
---------- 
     4    

 -n
----
  2

Term 2

  ((n * n) / 4 + n / 2) - ((n / 2) * (n / 2))
  
    n^2      n          n^2
   ----- +  ---   -  ( ----- )
     4       2           4
     
    n^2      2n         n^2
   ----- +  ---   -    ----- 
     4       4          4
     
    n^2   +   2n    -   n^2
   -------------------------- 
              4          
              
    2n
   ---- 
    4          
 
  n 
 --- 
  2

So, If I did no mistake, then the result is always n/2

Could be done with that:

#include <iostream> 

int main() {
    long long n{};
    if (std::cin >> n)
        std::cout << ((n%2)? (-n / 2):(n/2)) << '\n';
}
A M
  • 14,694
  • 5
  • 19
  • 44