Sum of big numbers

[Omaewabanani]

Hello. I really need help with a program. I need to output a sum of all n digit numbers. So like if I make n=100, I need to output a sum of all 100 digit numbers. Can anyone help me with that?

[mbozzi]

The sum of the first m natural numbers can be shown to be sum(m) = (m (m + 1) / 2).
All n-digit numbers of the same sign are contiguous. Therefore the sum of all n-digit natural numbers is given by sum((10 ^ n) - 1) - sum(10 ^ (n - 1) - 1).

For example, the sum of all 2-digit natural numbers is the sum of the first 99 natural numbers minus the sum of the first 9 natural numbers:
sum((10 ^ 2) - 1) - sum(10 ^ (2 - 1) - 1) = sum(99) - sum(9) = 99 * 100 / 2 - (9 * 10 / 2) = 4950 - 45 = 4905

[lastchance]

For n=100, ....
49499999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

[Omaewabanani]

Yep, I get that, but how do I calculate and output it? Its pretty big number and I am sure that int or long long cant contain it.

[helios]

You'll need to write a class that can store and manipulate big numbers.

class BigInteger{
    //...
public:
    BigInteger(int n = 0); //construct from a value
    BigInteger(const char *); //construct from a string
    BigInteger operator+(const BigInteger &) const;
    BigInteger operator-(const BigInteger &) const;
    BigInteger operator*(const BigInteger &) const;
    std::string to_string() const;
};

That should be enough to do what you need. To implement the overloads, I recommend using the algorithms you learned in primary school. You should design your data representation (e.g. an array of chars? An array of ints?) so that it makes implementing the algorithms as easy as possible.

[lastchance]

I didn't use a class of big integers. You don't need to manipulate the number ... just print it.

Use @mbozzi's formula, a lot of algebra, and note that powers of 10 give long sequences of 0's and if you subtract something from them, long sequences of 9's. You can then get a string representation.

For n >= 4 it will come out as
494 ..... certain number of 9's ..... 55 ....... certain number of 0's

(At least I checked from n=4 to 9 by direct computation, then presumed it worked thereafter.)