main.cpp

// Either include the necessary headers or use a single header file

// #include <iostream>
// #include <vector>
// #include <string>
// #include <algorithm>
// #include <sstream>

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

class BigInteger
{
private:
    vector<int> digits;
    bool isNegative;

    // Function to remove leading zeros
    void removeLeadingZeros()
    {
        while (digits.size() > 1 && digits.back() == 0)
        {
            digits.pop_back();
        }
        // If the number becomes zero, ensure it's positive
        if (digits.size() == 1 && digits[0] == 0)
        {
            isNegative = false;
        }
    }

    // Function to compare absolute values
    int compareAbsolute(const BigInteger &other) const
    {
        if (digits.size() > other.digits.size())
        {
            return 1;
        }
        if (digits.size() < other.digits.size())
        {
            return -1;
        }

        for (int i = digits.size() - 1; i >= 0; i--)
        {
            if (digits[i] > other.digits[i])
            {
                return 1;
            }
            if (digits[i] < other.digits[i])
            {
                return -1;
            }
        }
        return 0;
    }

    // Function for addition
    BigInteger addAbsolute(const BigInteger &other) const
    {
        BigInteger result;
        result.digits.clear();
        result.isNegative = false;

        int carry = 0;
        size_t maxSize = max(digits.size(), other.digits.size());

        for (size_t i = 0; i < maxSize || carry; i++)
        {
            int sum = carry;
            if (i < digits.size())
            {
                sum += digits[i];
            }
            if (i < other.digits.size())
            {
                sum += other.digits[i];
            }

            result.digits.push_back(sum % 10);
            carry = sum / 10;
        }

        return result;
    }

    // Function for subtraction (assumes this >= other)
    BigInteger subtractAbsolute(const BigInteger &other) const
    {
        BigInteger result;
        result.digits.clear();
        result.isNegative = false;

        int borrow = 0;
        for (size_t i = 0; i < digits.size(); i++)
        {
            int diff = digits[i] - borrow;
            if (i < other.digits.size())
            {
                diff -= other.digits[i];
            }

            if (diff < 0)
            {
                diff += 10;
                borrow = 1;
            }
            else
            {
                borrow = 0;
            }

            result.digits.push_back(diff);
        }

        result.removeLeadingZeros();
        return result;
    }

public:
    // Default constructor
    BigInteger() : isNegative(false)
    {
        digits.push_back(0);
    }

    // Constructor from integer
    BigInteger(long long num) : isNegative(num < 0)
    {
        if (num == 0)
        {
            digits.push_back(0);
            isNegative = false;
            return;
        }

        if (num < 0)
        {
            num = -num;
        }

        while (num > 0)
        {
            digits.push_back(num % 10);
            num /= 10;
        }
    }

    // Constructor from string
    BigInteger(const string &str)
    {
        if (str.empty())
        {
            digits.push_back(0);
            isNegative = false;
            return;
        }

        size_t start = 0;
        isNegative = false;

        if (str[0] == '-')
        {
            isNegative = true;
            start = 1;
        }
        else if (str[0] == '+')
        {
            start = 1;
        }

        if (start >= str.length())
        {
            digits.push_back(0);
            isNegative = false;
            return;
        }

        // Store digits in reverse order (least significant first)
        for (int i = str.length() - 1; i >= (int)start; i--)
        {
            if (str[i] >= '0' && str[i] <= '9')
            {
                digits.push_back(str[i] - '0');
            }
        }

        if (digits.empty())
        {
            digits.push_back(0);
            isNegative = false;
        }
        else
        {
            removeLeadingZeros();
        }
    }

    // Copy constructor
    BigInteger(const BigInteger &other) : digits(other.digits), isNegative(other.isNegative) {}

    // Assignment operator
    BigInteger &operator=(const BigInteger &other)
    {
        if (this != &other)
        {
            digits = other.digits;
            isNegative = other.isNegative;
        }
        return *this;
    }

    // Addition operator
    BigInteger operator+(const BigInteger &other) const
    {
        if (isNegative == other.isNegative)
        {
            BigInteger result = addAbsolute(other);
            result.isNegative = isNegative;
            return result;
        }
        else
        {
            int cmp = compareAbsolute(other);
            if (cmp == 0)
            {
                return BigInteger(0);
            }
            else if (cmp > 0)
            {
                BigInteger result = subtractAbsolute(other);
                result.isNegative = isNegative;
                return result;
            }
            else
            {
                BigInteger result = other.subtractAbsolute(*this);
                result.isNegative = other.isNegative;
                return result;
            }
        }
    }

    // Subtraction operator
    BigInteger operator-(const BigInteger &other) const
    {
        if (isNegative != other.isNegative)
        {
            BigInteger result = addAbsolute(other);
            result.isNegative = isNegative;
            return result;
        }
        else
        {
            int cmp = compareAbsolute(other);
            if (cmp == 0)
            {
                return BigInteger(0);
            }
            else if (cmp > 0)
            {
                BigInteger result = subtractAbsolute(other);
                result.isNegative = isNegative;
                return result;
            }
            else
            {
                BigInteger result = other.subtractAbsolute(*this);
                result.isNegative = !isNegative;
                return result;
            }
        }
    }

    // Multiplication operator
    BigInteger operator*(const BigInteger &other) const
    {
        BigInteger result;
        result.digits.assign(digits.size() + other.digits.size(), 0);
        result.isNegative = (isNegative != other.isNegative);

        for (size_t i = 0; i < digits.size(); i++)
        {
            int carry = 0;
            for (size_t j = 0; j < other.digits.size() || carry; j++)
            {
                long long prod = result.digits[i + j] + carry;
                if (j < other.digits.size())
                {
                    prod += (long long)digits[i] * other.digits[j];
                }
                result.digits[i + j] = prod % 10;
                carry = prod / 10;
            }
        }

        result.removeLeadingZeros();
        return result;
    }

    // Division operator (integer division)
    BigInteger operator/(const BigInteger &other) const
    {
        if (other.isZero())
        {
            throw runtime_error("Division by zero");
        }

        if (compareAbsolute(other) < 0)
        {
            return BigInteger(0);
        }

        BigInteger dividend = *this;
        dividend.isNegative = false;
        BigInteger divisor = other;
        divisor.isNegative = false;

        BigInteger result;
        result.digits.assign(digits.size(), 0);

        BigInteger current;
        current.digits.clear();

        for (int i = digits.size() - 1; i >= 0; i--)
        {
            current.digits.insert(current.digits.begin(), digits[i]);
            current.removeLeadingZeros();

            int count = 0;
            while (current.compareAbsolute(divisor) >= 0)
            {
                current = current.subtractAbsolute(divisor);
                count++;
            }
            result.digits[i] = count;
        }

        result.isNegative = (isNegative != other.isNegative);
        result.removeLeadingZeros();
        return result;
    }

    // Modulo operator
    BigInteger operator%(const BigInteger &other) const
    {
        return *this - (*this / other) * other;
    }

    // Comparison operators
    bool operator==(const BigInteger &other) const
    {
        return isNegative == other.isNegative && digits == other.digits;
    }

    bool operator!=(const BigInteger &other) const
    {
        return !(*this == other);
    }

    bool operator<(const BigInteger &other) const
    {
        if (isNegative != other.isNegative)
        {
            return isNegative;
        }

        int cmp = compareAbsolute(other);
        return isNegative ? cmp > 0 : cmp < 0;
    }

    bool operator>(const BigInteger &other) const
    {
        return other < *this;
    }

    bool operator<=(const BigInteger &other) const
    {
        return !(*this > other);
    }

    bool operator>=(const BigInteger &other) const
    {
        return !(*this < other);
    }

    // Unary operators
    BigInteger operator-() const
    {
        BigInteger result = *this;
        if (!isZero())
        {
            result.isNegative = !result.isNegative;
        }
        return result;
    }

    BigInteger operator+() const
    {
        return *this;
    }

    // Compound assignment operators
    BigInteger &operator+=(const BigInteger &other)
    {
        *this = *this + other;
        return *this;
    }

    BigInteger &operator-=(const BigInteger &other)
    {
        *this = *this - other;
        return *this;
    }

    BigInteger &operator*=(const BigInteger &other)
    {
        *this = *this * other;
        return *this;
    }

    BigInteger &operator/=(const BigInteger &other)
    {
        *this = *this / other;
        return *this;
    }

    BigInteger &operator%=(const BigInteger &other)
    {
        *this = *this % other;
        return *this;
    }

    // Utility functions
    bool isZero() const
    {
        return digits.size() == 1 && digits[0] == 0;
    }

    bool isPositive() const
    {
        return !isNegative && !isZero();
    }

    bool isNegativeValue() const
    {
        return isNegative;
    }

    string toString() const
    {
        if (isZero())
        {
            return "0";
        }

        string result;
        if (isNegative)
        {
            result += "-";
        }

        for (int i = digits.size() - 1; i >= 0; i--)
        {
            result += (char)('0' + digits[i]);
        }

        return result;
    }

    // Power function (for positive exponents)
    BigInteger power(int exp) const
    {
        if (exp < 0)
        {
            throw runtime_error("Negative exponent not supported");
        }
        if (exp == 0)
        {
            return BigInteger(1);
        }

        BigInteger result(1);
        BigInteger base = *this;

        while (exp > 0)
        {
            if (exp % 2 == 1)
            {
                result *= base;
            }
            base *= base;
            exp /= 2;
        }

        return result;
    }

    // GCD function
    BigInteger gcd(const BigInteger &other) const
    {
        BigInteger a = *this;
        BigInteger b = other;
        a.isNegative = false;
        b.isNegative = false;

        while (!b.isZero())
        {
            BigInteger temp = b;
            b = a % b;
            a = temp;
        }

        return a;
    }

    // Stream output operator
    friend ostream &operator<<(ostream &os, const BigInteger &num)
    {
        os << num.toString();
        return os;
    }

    // Stream input operator
    friend istream &operator>>(istream &is, BigInteger &num)
    {
        string str;
        is >> str;
        num = BigInteger(str);
        return is;
    }
};

// main function with some default examples
int main()
{
    cout << "=== BigInteger Class Demo ===" << endl;

    // Test basic operations
    BigInteger a("123456789012345678901234567890");
    BigInteger b("987654321098765432109876543210");

    cout << "a = " << a << endl;
    cout << "b = " << b << endl;
    cout << endl;

    // Addition
    cout << "Addition:" << endl;
    cout << "a + b = " << a + b << endl;
    cout << endl;

    // Subtraction
    cout << "Subtraction:" << endl;
    cout << "b - a = " << b - a << endl;
    cout << "a - b = " << a - b << endl;
    cout << endl;

    // Multiplication
    cout << "Multiplication:" << endl;
    // BigInteger c("123456789");
    // BigInteger d("987654321");
    BigInteger c("864197532086419753208641975320");
    BigInteger d("864197532086419753208641975320");
    cout << c << " * " << d << " = " << c * d << endl;
    cout << endl;

    // Division
    cout << "Division:" << endl;
    cout << b << " / " << a << " = " << b / a << endl;
    cout << b << " % " << a << " = " << b % a << endl;
    cout << endl;

    // Power
    cout << "Power:" << endl;
    BigInteger e("12345");
    cout << e << "^3 = " << e.power(3) << endl;
    cout << endl;

    // Comparison
    cout << "Comparison:" << endl;
    cout << "a == b: " << (a == b) << endl;
    cout << "a < b: " << (a < b) << endl;
    cout << "a > b: " << (a > b) << endl;
    cout << endl;

    // Negative numbers
    cout << "Negative numbers:" << endl;
    BigInteger f("-123456789");
    BigInteger g("987654321");
    cout << f << " + " << g << " = " << f + g << endl;
    cout << f << " * " << g << " = " << f * g << endl;
    cout << endl;

    // GCD
    cout << "GCD:" << endl;
    BigInteger h("48");
    BigInteger i("18");
    cout << "gcd(" << h << ", " << i << ") = " << h.gcd(i) << endl;

    return 0;
}