long integer is out of range negative product

Question

I was trying to find product of some long long integer (0<=a[i]<=10^18)t. now how do i find that the product exeeds 10^18? does the product turn into negetive number (product<0)?

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    long long a[n],product=1;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    for(auto i:a){
        product*=i;
        if(i==0) break;
        if(product>1000000000000000000) {
            cout<<-1;
            return 0;
        }
    }
    cout<<product;
}

Answer 1

In my code, I use function isOverflow() to check it. You can search and go through std::numeric_limits<T>::max().

Additionally, since the first comments mentioned several questions about C++ practice, so I made some changes on your code for a better C++ coding habit and convention. I explained the reason by comments.

According to the suggestion of comments, I have removed VLA(Variable Length Array).

#include <algorithm> // for std::sort
#include <iostream>  // for std::cin, std::cout, std::endl
#include <limits>    // for std::numeric_limits

bool isOverflow(long long a, long long b)
{
    if (a == 0 || b == 0)
    {
        return false; // No overflow can occur with zero operands
    }

    if (a > std::numeric_limits<long long>::max() / b)
    {
        return true; // Overflow detected
    }

    return false;
}

int main()
{
    int n;
    std::cin >> n;
    long long product = 1;

    while (n > 0)
    {
        long long val;
        std::cin >> val;

        if (val < 0) // Since you mentioned that integer >= 0
        {
            std::cout << "Negative number is not allowed! Please re-enter!\n";
        }
        else if (val == 0)
        {
            product = 0;
            break;
        }
        else
        {
            if (isOverflow(product, val) == false)
            {
                product *= val;
                n--; // Count the number of valid input.
            }
            else
            {
                std::cout << "The product is overflowed" << std::endl;
                // Easier to understand than just print -1.
                return 0;
            }
        }
    }

    std::cout << "The product is " << product << std::endl;

    return 0;
}

Answer 2

If you are to check against potential overflow, I would advise you to rely on std::numeric_limits<>::max() (from the <limits> header) instead of a power of 10 (because the latter eliminates (a lot) of valid values).

Another advantage is portability. Indeed, in your code, you assume that long long is 8 bytes long which may not always be the case on another platform. Using std::numeric_limits<>::max() would guarantee to get the right maximum for the specified numeric type.

---

"Does the product turn into negative number ?"

Actually, signed overflow is Undefined Behaviour so anything can happen. It may be negative, it may not, old legends say that you can even get demons flying out of your nose :D

In case of Undefined Behaviour, it's pointless to reason about the behaviour of the program, unless we look at the generated assembly code to see what will really happen.

"How do I find that the product doesn't overflow ?"

In other words, the question is, how to check if a * b > max ? (where max is std::numeric_limits<long long>::max()).

Well, as written, you can't, because by definition, you cannot represent anything higher than max and evaluating a*b would be undefined behaviour anyway.

But the above test can be rewritten as a > max / b (with b != 0). We turned the multiplication into a division, and consequently the test is now evaluable without overflow.

To avoid clutter in your code, you could perform the test into a dedicated function. Such function might be defined as follows:

#include <concepts>
#include <limits>
#include <cmath>

template <std::integral T>
bool verify_product_range(T a, T b)
{
    return (!b || std::abs(a) <= std::numeric_limits<T>::max()/std::abs(b)); // Returns false if a*b overflows, true otherwise.
}

^{Note: For the above example, the validity range excludes std::numeric_limits<T>::min(). See here for a more complete version (or below).}

---

Edit

A more complete version of the above example (taking into account std::numeric_limits<>::min() as well in the validity range) might be:

template <std::integral T>
bool verify_product_range(T a, T b)
{
    if(!b || !a)
        return true; // zero is always valid

    if(a/b > 0) // If the product is positive
        return (std::abs(a) <= std::numeric_limits<T>::max()/std::abs(b));
    
    else // else (if the product is negative)
    {
        if(b < 0) std::swap(a, b);

        return (a >= std::numeric_limits<T>::min()/b);
    }
}