We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Practice
  2. Algorithms
  3. Implementation
  4. Extra Long Factorials
  5. Discussions

Extra Long Factorials

  • tsuda_kageyu + 7 comments

    It's beyond my capacity to implement a complete BigInteger like class in C++, but I did this:

    #include <vector>
#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> d;
    d.push_back(1);
    
    for (int i = 2; i <= n; ++i) {
        for (auto it = d.begin(); it != d.end(); ++it)
            *it *= i;
        
        for (size_t j = 0; j < d.size(); ++j) {
            if (d[j] < 10)
                continue;

            if (j == d.size() - 1)
                d.push_back(0);
            
            d[j + 1] += d[j] / 10;
            d[j] %= 10;
        }
    }

    for (auto it = d.rbegin(); it != d.rend(); ++it)
        cout << *it;
    
    return 0;
}
    • VictoriaB + 0 comments

      Wow. This is nice!

    • aaron_coltrane + 0 comments

      Almost same as me

    • ashekhar + 1 comment

      Could you please explain the approach and why we are doing: d[j + 1] += d[j] / 10; d[j] %= 10;

      • squirrelwhisky + 0 comments

        He used the math multiplication method we used everyday when it's come to multiply two more-than-one-digit number: abc * ef = abc * e * 10 + abc * f . His approach is based on that but he's done it reversely. The way he did it is really clever!

    • clivic + 1 comment

      This solution is like mimicking the multiplication process in math, in other words, how you multiply 12 by 5: 

      first, 2 (in 12) by 5 is 10. Because 10/10 == 1, we got a 1 here.
second, 1 (in 12) by 5. Because we got a 1 before, we get 5+1 == 6 here.

      If you write it down on a paper following this code, you will get it.

      • squirrelwhisky + 0 comments

        Thank for you explaination. Appreciate that!

    • clivic + 0 comments

      A commented C++ version using the idea of "arithmatic carry" (the same idea this example used) is as following:

      void extraLongFactorials(int n) {
    if (n == 1) {
        cout << 1 << endl;
        return;
    }

    vector<int> digits(1, 1);
    for (int curr(2); curr <= n; ++curr) {
        auto digit_count = digits.size();

        // Every digit times the number.
        for (int i(0); i < digit_count; ++i) {
            digits[i] *= curr;
        }

        // From the units to tenths, hundreds...
        // Perform the carry.
        for (int i(0); i < digit_count; ++i) {
            auto carry = digits[i] / 10;
            digits[i] = digits[i] % 10;
            if (i != digit_count - 1) {
                // Add the carry to the next digit.
                digits[i + 1] += carry;
            } else {
                // New leftmost digit(s).
                if (carry > 0) {
                    int & remaining(carry);
                    do {
                        auto digit = remaining % 10;
                        remaining /= 10;
                        digits.push_back(digit);
                    } while (remaining > 0);
                }
            }
        }
    }

    // Print out the digits.
    for (auto it = digits.rbegin(); it != digits.rend(); ++it) {
        cout << *it;
    }
}
    • jtsaur + 0 comments
      [deleted]
    • ken771209 + 0 comments

      great idea