15
\$\begingroup\$
#include <iostream>
#include <cmath>
using namespace std;
int s = 1; //Serial No.

Should I use recursion for the factorials function?

int Factorial(int n)
{
    int k=1;
    for(int i=1;i<=n;++i)
    {
        k=k*i;
    }
    return k;
}

How I can go about doing this in a single for loop instead of the 3 while loops?

int main()
{
    int a = 1;
    int b = 1;
    int c = 1;
    int Fact1;
    int Fact2;
    int Fact3;
    while (a < 11)
    {
        Fact1 = Factorial(a);
        while (b < 11)
        {
            Fact2 = Factorial(b);
            while (c < 11)
            {
                Fact3 = Factorial(c);
                cout << s << " : ";
                int LHS = Fact1 + Fact2 + Fact3;
                if (LHS == a * b * c)
                {
                    cout << "Pass:" <<"    "<< a << " & " << b << " & " << c << endl;
                }
                else
                {
                    cout << "Fail" /*<<"   "<< Fact1 <<"   "<< Fact2 <<"   "<<Fact3*/<<endl;
                }
                    c++;
                    s++;
            }
            c = 1;
            b++;
        }
        b = 1;
        a++;
    }
    return 0;
}

Also I would love some variable naming tips.

\$\endgroup\$
  • 2
    \$\begingroup\$ I used 11 as the limit because I started writing the code in my mobile phone and the program I used to run it, "finished running" the code after the 1000th output \$\endgroup\$ – amaan797 Apr 15 at 9:18
  • 13
    \$\begingroup\$ Welcome to Code Review. I have rolled back your latest edits. Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Heslacher Apr 15 at 10:43
  • 2
    \$\begingroup\$ @amaan797 What are the solutions you got? \$\endgroup\$ – xxx--- Apr 15 at 11:50
  • 1
    \$\begingroup\$ Is this in reference to accepting an answer if so I have done that \$\endgroup\$ – amaan797 Apr 15 at 15:37
  • 2
    \$\begingroup\$ I understand this is code review, but without loss of generality 0<A<=B<=C, and A<B<C implies ABC<=C!<A!+B!+C! so either A=B or B=C or both. \$\endgroup\$ – user197649 Apr 15 at 22:33
26
\$\begingroup\$

Hello and welcome to Code Review.

Surprisingly, a, b, and c are probably the best variable names you can come up with. They are conventionally given as canonical examples of bad names, but when the task is to implement a mathematical function using the same variable names as in the spec is more important.

As to the single loop question, the short answer is "not easily". You are trying to check all combinations of three independently varying things. That means you naturally want three loops, and anything else would lose out on readability.


Aside from your questions, I have a few observations about this code that might be worth fixing.

  • When you have a loop that is counting up to something, it is convention to prefer a for loop to a while loop.
  • Factorial is what is known as a "pure function" which means that its output only depends on its input. Such functions within loops are often good candidates for caching so that you don't have to waste time calculating the same output a hundred and eleven times for each input number.
  • Both + and * are commutative, which means that if a, b, and c pass then b, a, and c also pass. You should check whether you need to display all reorderings of the same sets of numbers.
  • It is unclear where 11 has come from. It seems like a magic number, which would benefit from being moved to a named constant and having a comment explaining why that value is used.
\$\endgroup\$
  • 3
    \$\begingroup\$ You should check whether you need to display all reorderings of the same sets of numbers. You could expand this. Because this is true, you don't have to check them either, which means you can remove some of the iterations. If you do have to display, you can still do this, and just print all permutations afterwards. \$\endgroup\$ – JAD Apr 15 at 8:31
  • 7
    \$\begingroup\$ 7! = 1540 and 7^3 = 343, no need to check higher than 6. Could of course loop until n! > n^3. \$\endgroup\$ – JollyJoker Apr 15 at 13:54
  • 6
    \$\begingroup\$ @JollyJoker That observation is enough for a separate answer. I recommend pre-caching the limit as it's constant and faster to do so. \$\endgroup\$ – wizzwizz4 Apr 15 at 14:19
  • 1
    \$\begingroup\$ Someone better at c++ than me could do a discussion on what's better to cache / pre-calculate / hardcode, avoiding premature optimization and so on. Factorials of 1-7 are few, 343 loops is nothing etc. \$\endgroup\$ – JollyJoker Apr 15 at 14:46
  • \$\begingroup\$ @JollyJoker Are you sure 7! isn't 5040? Also, side-by-side: coliru.stacked-crooked.com/a/365eef0d85122710 \$\endgroup\$ – Deduplicator Apr 16 at 13:10
19
\$\begingroup\$

Avoid using namespace std. It doesn't even save any typing in this program.

serialNumber doesn't need to be global.

Consider using unsigned types for numbers when negatives can't be present.

Whilst there's nothing wrong with the factorial function (and I certainly wouldn't recommend making it recursive), we can skip the i==1 iteration:

constexpr unsigned int factorial(unsigned int n)
{
    unsigned int k = 1;
    for (unsigned int i = 2u;  i <= n;  ++i) {
        k *= i;
    }
    return k;
}

Note that we need to be very careful with our inputs to avoid overflow here. With a 16-bit int, we can compute factorials only up to 8!, and with 32-bit int, a maximum of 12!. Consider throwing a std::range_error when the output is too large to represent:

#include <limits>
#include <stdexcept>

constexpr unsigned int factorial(unsigned int n)
{
    unsigned int k = 1;
    for (unsigned int i = 2u;  i <= n;  ++i) {
        if (k >= std::numeric_limits<decltype(k)>::max() / n) {
            throw std::range_error("factorial");
        }
        k *= i;
    }
    return k;
}

Reduce scope of variables, and keep the names of related variables obviously connected; i.e. instead of using numbers for the factorials, include a, b or c in their names (e.g. fa, fb, fc).

We can reduce the search space by limiting the loops so that we don't repeat tests so much (given that both operations are commutative):

for (unsigned a = 1;  a < 11;  ++a)
{
    auto const fa = factorial(a);
    for (unsigned b = 1;  b <= a;  ++b)
    {
        auto const fb = factorial(b);
        for (unsigned c = 1;  c <= b;  ++c)
        {
            auto const fc = factorial(c);

Notice how the inner loops reach but don't exceed the current value of the containing loop.

Prefer '\n' to std::endl when there's no need to flush the output immediately (in fact, when a newline and flush are both needed, I prefer to write << '\n' << std::flush to be absolutely clear what we want).


Modified code

#include <iostream>
#include <limits>
#include <stdexcept>

constexpr unsigned int factorial(unsigned int n)
{
    unsigned int k = 1;
    for (unsigned int i = 2u;  i <= n;  ++i) {
        if (k >= std::numeric_limits<decltype(k)>::max() / n) {
            throw std::range_error("factorial");
        }
        k *= i;
    }
    return k;
}

int main()
{
    for (unsigned a = 1;  a < 11;  ++a) {
        auto const fa = factorial(a);
        for (unsigned b = 1;  b <= a;  ++b) {
            auto const fb = factorial(b);
            for (unsigned c = 1;  c <= b;  ++c) {
                auto const fc = factorial(c);
                if (fa + fb + fc == a * b * c) {
                    std::cout << "Pass:" << "    "
                              << a << " & " << b << " & " << c
                              << '\n';
                }
            }
        }
    }
}

Exercise

What would you change to extend this to search for N numbers whose product equals the sum of their factorials, when N is given at run time?

\$\endgroup\$
  • 2
    \$\begingroup\$ This answer is the most accurate/useful one IMO \$\endgroup\$ – polfosol Apr 15 at 11:10
  • 5
    \$\begingroup\$ Note that big names like Sutter and Stroustrup increasingly advise away from using unsigned. e.g. isocpp.github.io/CppCoreGuidelines/… \$\endgroup\$ – Josiah Apr 15 at 11:28
  • 5
    \$\begingroup\$ @Josiah, that link refers to something different - using unsigned doesn't magically enforce correctness of values. However, it does give more range than the corresponding signed type, and has well-defined overflow behaviour, so it's a mistake to think that unsigned types should be avoided. (That said, do avoid mixing signed and unsigned types in computation.) \$\endgroup\$ – Toby Speight Apr 15 at 11:56
  • 2
    \$\begingroup\$ I think the clearer presentation of their perspective is found in this panel video. youtube.com/watch?v=Puio5dly9N8#t=42m40s \$\endgroup\$ – Josiah Apr 15 at 13:32
  • 1
    \$\begingroup\$ An efficient factorial is important here, so putting an error check inside the inner loop seems like a mistake vs. precomputing (maybe with templates somehow) the max input we can handle without overflowing. Also, note that we can compute fb in terms of fa, just multiplying the numbers from a+1 to b. \$\endgroup\$ – Peter Cordes Apr 16 at 12:19
9
\$\begingroup\$

A couple of remarks in addition to Josiah's answer:

  • While I agree that the variable names a, b and c are fine when implementing mathy functions that can be concisely described with these identifiers, this doesn't apply to the counter s. I am not totally sure what it does, but

    int s = 1; //Serial No.
    

    makes me think that

    int serialNumber = 1;
    

    would be a better approach.

  • Try to be consistent in your naming, you have some names that start with an upper case and some that start with a lower case. Instead, pick one scheme and stick to it.

  • Keep the scope of your variables as small as possible.

    int Fact1;
    int Fact2;
    int Fact3;
    

    They can all be moved into the loop body and be initialized upon their declaration. This doesn't make the exist unitialized, which is desireable.

  • When you don't intend to modify a variable, const-qualify it:

    const int LHS = Fact1 + Fact2 + Fact3;
    
  • If you intend to enlarge the 11 constant at some point, note that factorials might get quite large. Maybe check (if the limit is known at compile time via a static_assert) that Fact1, Fact2 and Fact3 as well as the sum of it can't overflow?

  • I don't see any use of functions that come from

    #include <cmath>
    

    so you might want to remove this line.

\$\endgroup\$
  • 10
    \$\begingroup\$ I think 11 is way to big already. Assume(without loss of generality) that c>=b>=a; We know that abc>c!, or a*b>(c-1)!, so b>sqrt(c-1)!. Because the square root of 5! is more than 6 we can know that the equation is not satisfiable with c>=6 \$\endgroup\$ – Taemyr Apr 15 at 9:05
  • 4
    \$\begingroup\$ Taemyr, that is an excellent point and a good example of a bit of maths saving a lot of crunching. My only worry is that it may get missed as a comment. \$\endgroup\$ – Josiah Apr 15 at 11:23
  • 4
    \$\begingroup\$ @Taemyr make that into an answer, focusing on how to understand and translate the requirements into code (as opposed to code style) \$\endgroup\$ – Baldrickk Apr 15 at 11:28
  • 2
    \$\begingroup\$ I'd add: separate the code to list tuples {a,b,c} from the code to test a tuple. \$\endgroup\$ – YSC Apr 15 at 13:35
6
\$\begingroup\$

Don't forget testability

As no other answer has mentioned this - I feel it's worth pointing out by itself.

In your current example, you are writing the results directly to stdout as soon as they are found. This works well for toy examples, and as it gives you the output you desire - it's often an easy habit to get into.

However, doing it this way requires a human to verify and test the output each time a change is made.

Instead of writing results directly to stdout; try to separate the business logic from the output itself. That is, write the logic in a function which returns the results. In this specific case, you may want to return a list/vector of structs, representing each result as calculated:

   struct Result {  
       bool success;  
       int input_a;  
       int input_b;  
       int input_c;  
       int calculated_abc;  
       int calculated_fa_fb_fc_total;     
    };

Once separate, you'll have a function that can be run by "other code" (such as in a test framework), allowing you to write automated tests that check this code is always correct for a given set of inputs.

\$\endgroup\$
3
\$\begingroup\$

The code as presented suffers from an algorithmic problem known as The Algorithm of Shlemiel the Painter. For example, after calculating 5! = 120 and going on to calculate 6!, the Factorial function has to determine 1×2×3×4×5×6, even though it has just been calculated what the product of the first five terms is. Not particularly important in this particular case because the numbers involved are so small, but it’s still something to be kept in mind. To address this concern, storing the last value of the factorial is helpful as then a single multiplication operation suffices to find out the new value.

Additionally, because the expression is symmetric, it’s only necessary to look for solutions where a ≥ b ≥ c. All other solutions will be permutations of what was found.

With that in mind, the code can be simplified just to this:

#include <iostream>

int main()
{
    int const MAX = 11;
    for(int a = 0, af = 1; a < MAX; af *= ++a)
    {
        for(int b = 0, bf = 1; b <= a; bf *= ++b)
        {
            for(int c = 0, cf = 1; c <= b; cf *= ++c)
            {
                if(af + bf + cf == a * b * c)
                {
                    std::cout << "a: " << a << std::endl;
                    std::cout << "b: " << b << std::endl;
                    std::cout << "c: " << c << std::endl;
                    std::cout << std::endl;
                }
            }
        }
    }

A more advanced technique would be to factor out the generation of the factorial sequence. Alas, without C++20 coroutines it’s clumsy. The main function becomes very pretty and clear:

int main()
{
    int const MAX = 11;
    for(auto [a, af] : factorials_upto{MAX})
    {
        for(auto [b, bf] : factorials_upto{a + 1})
        {
            for(auto [c, cf] : factorials_upto{b + 1})
            {
                if(af + bf + cf == a * b * c)
                {
                    std::cout << "a: " << a << std::endl;
                    std::cout << "b: " << b << std::endl;
                    std::cout << "c: " << c << std::endl;
                    std::cout << std::endl;
                }
            }
        }
    }
}

but the code enabling that is less so:

#include <tuple>

class factorial_iterator
{
public:
    factorial_iterator(int value): m_value{value}, m_product{1}
    {
    }

    std::tuple<int, int> operator *() const
    {
        return { m_value, m_product };
    }

    factorial_iterator& operator ++()
    {
        m_product *= ++m_value;

        return *this;
    }

    bool operator !=(factorial_iterator const& other) const
    {
        return m_value != other.m_value;
    }

private:
    int m_value;
    int m_product;
};

struct factorials_upto
{
    int m_end;

    friend factorial_iterator begin(factorials_upto const &)
    {
        return {0};
    }

    friend factorial_iterator end(factorials_upto const& fu)
    {
        return {fu.m_end};
    }
};
\$\endgroup\$
  • 2
    \$\begingroup\$ It's probably much easier just to pre-compute an array of (all?) factorials which can be expressed in the target type, and use that. \$\endgroup\$ – Deduplicator Apr 16 at 12:18
  • \$\begingroup\$ @Deduplicator: multiply is cheap on modern hardware; a lookup table isn't worth it. Strength-reduction of factorial to multiply is exactly what I was going to suggest if there wasn't already an answer pointing it out. The compiler can and probably will take care of strength-reducing a*b*c to prod += a*b; and of course hoisting the a*b and af+bf loop invariants. In theory the compiler could inline and optimize the factorial function calls, too, but I'd be less optimistic about that. \$\endgroup\$ – Peter Cordes Apr 16 at 12:32
  • \$\begingroup\$ @PeterCordes I would write a factorial array for clarity. \$\endgroup\$ – Martin Bonner supports Monica Apr 16 at 13:03
  • \$\begingroup\$ It's simple enough to simply write it yourself, see: coliru.stacked-crooked.com/a/365eef0d85122710 \$\endgroup\$ – Deduplicator Apr 16 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.