Reduce the complexity

Question

1.00/5 (1 vote)

See more:

good: A number n is called good if the sum of its proper divisors is more than n. Example sum of proper divisors of 12 is 1 + 2 + 3 + 4 + 6 = 16, which means that 12 is a good number.Given n, find the sum of all the good numbers less than or equal to n

What I have tried:

C++

int getResult(int n)
    {
    int a = 0;
    for (int i = 1; i <= sqrt(n); i++)
        {
        if (n % i == 0)
            {
            if (n / i == i)
                {
                a = a + i;
                }
            else
                {
                a = a + i;
                a = a + (n / i);
                }
            }
        }
    a = a - n;
    return a;

    }
int main()
    {
    int n;
    cin > > n;
    int final_sum = 0;
    for (int i = 1;
    i <= n; i++)
        {
        int sum = 0;
        sum = getResult(i);
        if (sum > i)
            final_sum += i;

        }
    cout < < final_sum;
    return (0);
    }

Posted 29-Aug-20 22:40pm

Member 14925633

Updated 31-Aug-20 23:15pm

OriginalGriff

v3

Add a Solution

6 solutions

Solution 5

First of all, there are a number of issues with your question. You could have avoided most of them by just reading and following the advice offered when entering your question here! By not doing so you're making it harder for anyone willing to help, and, as a result, the likelyhood of someone responding with a useful answer is considerably less.

Besides, making it easier for the people who try to help you is a matter of respect. If you just dump your code here, that is disrepectful toward those who are supposed to help you! Please put in some more effort next time you ask a question.

Second, when you post a question, do add the actual question to your code! We can't read your mind, nor do we see your screen, or the original task description that you are working on! Describe the result you get, and the result you expect, as well as any error messages you are seeing. Any part of that info that you omit will just leave us in the dark and will likely result in suggestions that don't help you.

Third, when you write code, do yourself and everyone else a favor and use names that are self-explanatory! "getResult" or "a" aren't useful at all! Use names that offer an insight about what they are used for, e. g. "sumOfDivisors". In case of "a", "sum_of_divisors" would also be a fitting name, but since that is exactly what the function does, you could simply name it "result", implying that this is the variable to store the sum of divisors. You did use "sum" and "final_sum" in your main function, but in this case the prefix "final" doesn't help in clarifying the difference between the two, as you are summing totally different numbers! "sum" should be "sum_of_divisors" and "final_sum" should be "sum_of_good_numbers" - that would instantly clarify what you are storing and calculating here!

Last, for performance, try these things:

1. Learn to use a profiler. You can of course try and make an educated guess which parts of your code take the most time, but even very experienced programmers tend to experience surprises when an actual profiler tells them where to look. The main reason for that is that modern compilers are typically much better at recognizing and optimizing inefficient code segments than the programmers themselves, and the performance bottlenecks that remain after compiler optimizations are much harder to spot.

2. The first thing to look at when you have performance issues, is redundand code, and that means, first, and foremost, code within loops - since that is code that is executed repeatedly. Check whether the loop code contains any statements that could be moved outside the loop. Calculating them once, before the start of the loop saves you needless repetitions of the same calculations. Note that any calculations performed within the for statement (or the conditions in do and while loops) are part of that loop code!

Example:
- your comparison i<=sqrt(n) is performed for every iteration. You could move the calculation invoked in that comparison out of the loop.
- you could calculate n/i just once and store it in a helper variable, or adjust your code that you don't need to recaluclate it multiple times.

3. check whether your loop code contains any nontrivial calculations or function calls. Consider replacing these with something more efficient.

Example, when you make a comparison involving stuff like square roots or divisions, try to reformulate them in such a manner that they use multiplications instead. E.g. instead of i<=sqrt(n), you could write i*i<=n. Of course, in this case, if you move the sqrt calculation outside the loop, it would be just one sqrt, but if you reform the comparison using i*i, then you have many multiplications, which may in this case not be an improvement! So be careful where to use this idea.

4. Function calls are considerably more time consuming than simple operations like * or /. When you have a function call inside a loop, check whether declaring it inline helps.

Example: your main function calls getResult() in a loop. Try declaring getResult() as inline.

5. When you have a loop, think about ways to reuse results from earlier iterations to help calculate results for later iterations.

Example: for every even number n=2*k, the divisors of k are also divisors of n. Warning: it's not trivial to find all additional divisors, and it requires storing the divisors of previous numbers - that could require a large amount of memory and just to maintan that memory might cost more performance than you could gain. However, if you think along the original idea, you could come up with an entirely different algorithm:

Instead of finding all divisors of all numbers up to n, construct all 'good' numbers n by combining divisors! For this idea it is useful to have heard of "Gödel numbering[^]" Basically this is an encoding that represents a given number n by its prime factors. E. g. the number 12 has the Gödel code {"2","1"} because 12=2^2*3^1, and 15 has the Gödel code {"0","1","1"} because 15=2^0*3^1*5^1.

The nice thing about Gödel representations is that calculating the sum of divisors is a lot easier. The bad thing is that, while you can enumerate (or order) numbers using their Gödel codes, that ordering does not correspond to the natural order of the actual numbers. Therefore it's a bit tricky to enumerate "all numbers up to N"

I'm not going to outline the (rather complex) steps for implementing this solution, as I don't think the author of this task was actually aiming for such a solution. Instead I'm going to suggest.

6. Use parallelization to improve your performance. Like 5, this might not be something the author of the task was aiming for. But if he did, simply use multiple threads to call getResult() for different numbers in your main loop.

Posted 31-Aug-20 23:04pm

Stefan_Lang

Updated 31-Aug-20 23:07pm

v2

Comments

Maciej Los 2-Sep-20 9:58am

5ed!

Stefan_Lang 2-Sep-20 11:47am

Thanks.

Solution 1

First off: indent your code!
I've edited you question to add indentation, but you should always ensure your code is correctly indented using your preferred style: Whitespiths, K&R, even 1TB if you must!It makes your code so much easier to read and understand.

Second, when you ask a question tell us what your code does that you didn't expect, or doesn't do that you did. Tell use any error messages and where they occur. Tell us what you did to make it do that. Tell us what you have tried to fix it. Just dumping your code on us and effectively saying "it don't work" doesn't help anyone!

And finally: getting your code working is part of the task: any chimp can bash out code, and get it to compile - but that's only the start! Compiling does not mean your code is right! :laugh:
Think of the development process as writing an email: compiling successfully means that you wrote the email in the right language - English, rather than German for example - not that the email contained the message you wanted to send.

So now you enter the second stage of development (in reality it's the fourth or fifth, but you'll come to the earlier stages later): Testing and Debugging.

Start by looking at what it does do, and how that differs from what you wanted. This is important, because it give you information as to why it's doing it. For example, if a program is intended to let the user enter a number and it doubles it and prints the answer, then if the input / output was like this:

Input   Expected output    Actual output
  1            2                 1
  2            4                 4
  3            6                 9
  4            8                16

Then it's fairly obvious that the problem is with the bit which doubles it - it's not adding itself to itself, or multiplying it by 2, it's multiplying it by itself and returning the square of the input.
So with that, you can look at the code and it's obvious that it's somewhere here:

C#

int Double(int value)
   {
   return value * value;
   }

Once you have an idea what might be going wrong, start using the debugger to find out why. Put a breakpoint on the first line of the method, and run your app. When it reaches the breakpoint, the debugger will stop, and hand control over to you. You can now run your code line-by-line (called "single stepping") and look at (or even change) variable contents as necessary (heck, you can even change the code and try again if you need to).
Think about what each line in the code should do before you execute it, and compare that to what it actually did when you use the "Step over" button to execute each line in turn. Did it do what you expect? If so, move on to the next line.
If not, why not? How does it differ?
Hopefully, that should help you locate which part of that code has a problem, and what the problem is.
This is a skill, and it's one which is well worth developing as it helps you in the real world as well as in development. And like all skills, it only improves by use!

Posted 29-Aug-20 23:23pm

OriginalGriff

Solution 3

I see that you have basically reposted this question from here[^].

If it's still timing out, be aware that sqrt may be a fairly expensive procedure call. Can you think of a more efficient way to terminate the loop?

Posted 30-Aug-20 8:07am

Greg Utas

Solution 4

I am not sure what your code was doing. This sequence can be simplified.

C++

if (n % i == 0)
    {
    if (n / i == i)
        {
        a = a + i;
        }
    else
        {
        a = a + i;
        a = a + (n / i);
        }
    }

To begin, "a = a + 1" is repeated twice. More importantly, why is a incremented by (n/1) when n/i does not equal i? Why is any of this code there? When i is a divisor of n you just want to increment the sum and then move on to the next value. This code should look like :

C++

if( n % i == 0 )
{
    a += i;
}

Why does it need to do anything else?

Another thing, the for loop is not correct. Since 6 is a divisor of 12, your loop would miss checking it. I think the loop's conditional statement should be i <= n / 2;. These two things should give your code better results.

Posted 30-Aug-20 11:00am

Rick York

Updated 30-Aug-20 11:02am

v2

Comments

Patrice T 30-Aug-20 17:50pm

I fear you need to reread the code carefully.
In "a = a + i;", 'i' is a letter, not a digit. And same with code in your solution.
This "(n / i == i)" is true when 'i' is the square root of 'n'.
"Since 6 is a divisor of 12" When factor 2 is found, "a = a + (n / i);" takes care of factor 6

Solution 6

Usually the trick is memoization, see Memoization - Wikipedia[^].

Posted 31-Aug-20 23:16pm

CPallini

Comments

Patrice T 1-Sep-20 8:41am

Hi,
What is the interest of memoization in this case ?
it is a 1 shoot search of divisors of numbers.

CPallini 1-Sep-20 9:12am

Recording divisors.

Stefan_Lang 1-Sep-20 12:07pm

While I did suggest storing divisors (and reuse them for multiples of that number), it's far from obvious how to find the additional divisors without accidentally including duplicates. In fact, I'm not sure it would help a lot - but that would require some testing.

IMHO that test is deliberately using a compiler with optimization turned off, to measure the ability of the programmer to find minor optimizations such as avoiding duplicate calculations.

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Patrice T · Accepted Answer · 2020-08-29T23:52:00

Quote:
Reduce the complexity

First you need to understand where your code is spending time and the reason.
A profiler will help you: Profiling (computer programming) - Wikipedia[^]
You need to understand the reason why some code is there and think about other ways to get to solution.
Example: "a = a - n;" is there only as a consequence of 1 as divisor, but 1 is always a divisor:

C++

int getResult(int n)
    {
    int a = 0;
    int a = 1;
    for (int i = 1; i <= sqrt(n); i++)
    for (int i = 2; i <= sqrt(n); i++)
        {
        if (n % i == 0)
            {
            if (n / i == i)
                {
                a = a + i;
                }
            else
                {
                a = a + i;
                a = a + (n / i);
                }
            }
        }
    a = a - n;
    return a;
    }

Reduce the complexity

6 solutions

Solution 5

Solution 2

Solution 1

Solution 3

Solution 4

Solution 6

Add your solution here

Preview 0

Reduce the complexity

6 solutions

Solution 5

Solution 2

Solution 1

Solution 3

Solution 4

Solution 6

Add your solution here

Preview 0

Existing Members

...or Join us