-2

Below is the problem question.
https://leetcode.com/problems/four-divisors/

I need a more optimized code.The below code exceeds the time limit.Please suggest me some edits to make this code more optimized.

My solution:

class Solution {
public:
    int sumFourDivisors(vector<int>& nums) {
        vector<int> ans;
        int x=0;

        for(int i=0;i<nums.size();i++){
            int j=1;
            while(j!=nums[i]+1){
                if(nums[i]%j==0){
                    ans.push_back(j);

                }
                j++;
            }

                if(ans.size()==4){
                     x=accumulate(ans.begin(),ans.end(),x);
                     ans.clear();


                }
               else
                   ans.clear();

         }
        return x;
    }
};
Jay Mathew
  • 1
  • 1
  • please explain to your rubber duck: When do you call `clear` and why? Alternatively you can use a debbugger to step through your code to see what is going wrong – 463035818_is_not_an_ai Mar 30 '20 at 10:45
  • You know the input and the expected output. That should make it very easy to create a small test-program that calls your code, and which you can use to *debug* your code. For example with a *debugger* you can step through your code statement by statement while monitoring variables and their values. That will make it easy to see when something goes wrong. – Some programmer dude Mar 30 '20 at 10:45
  • @idclev463035818 clear() clears the ans vector which contains the calculated divisors.I did so to avoid pushing all the divisors at once in the vector ans so that everytime for each nums[i] the divsors gets freshly pushed and if vector's size is 4, I could simply calculate its sum. – Jay Mathew Mar 30 '20 at 10:56
  • 1
    But you don't clear when you have an answer. You should clear always (or just move the `ans` vector declaration inside the loop). Just remove `else` in other words. – john Mar 30 '20 at 10:57
  • @JayMathew To be fair, I had to use my debugger to figure out the problem. You should learn how to do the same. I promise you that learning to use a debugger will be the single biggest improvement in your productivity as a programmer that you will ever make. – john Mar 30 '20 at 11:00
  • Yes,@john you're right.I need to have another `ans.clear()` after `x=accumulate(ans.begin(),ans.end(),x);`.Thank you.Can you suggest me ways of optimising this code. – Jay Mathew Mar 30 '20 at 11:02
  • @john Which debugger you use?I mean can you tell me which software you use to compile and debug your code.As I use online IDE where there's no feature of debugging. – Jay Mathew Mar 30 '20 at 11:07
  • why did you edit the question to remove any reference to the wrong result? The code in your question still produces wrong results, no? – 463035818_is_not_an_ai Mar 30 '20 at 11:10
  • Yes @idclev463035818 I rectified it and the code is correct now.Now the problem with this code is that it exceeds time limit so I updated my question. – Jay Mathew Mar 30 '20 at 11:13
  • in that case the question basically boils down to efficiently find divisors: https://stackoverflow.com/questions/26753839/efficiently-getting-all-divisors-of-a-given-number – 463035818_is_not_an_ai Mar 30 '20 at 11:17
  • In the future, when you have a different question to ask then please post a *new* question. And the edit you made *is* making it into a whole new question. The comment by @idclev463035818 should really have been written as an answer, and once you get an answer changing the question makes posted answers (and comments) worthless and possibly even wrong. Please take some time to read [the help pages](http://stackoverflow.com/help), take the SO [tour], read [ask], as well as [this question checklist](https://codeblog.jonskeet.uk/2012/11/24/stack-overflow-question-checklist/). – Some programmer dude Mar 30 '20 at 11:23
  • Also, your current and new question would be a better fit on [the codereview SE site](https://codereview.stackexchange.com/help/on-topic) ***if*** it works (that's a hard requirement). – Some programmer dude Mar 30 '20 at 11:24
  • @JayMathew The debugger you use is determined by the compiler/IDE that you use. So whatever you are using it should come with it's own debugger. – john Mar 30 '20 at 11:50
  • @JayMathew These code competitions always come down to using a smarter algorithm. So the code doesn't need optimising as such, you need to rewrite it to use a different technique. What that would be I'm not certain. – john Mar 30 '20 at 11:53
  • Please include the problem statement, or a synopsis of it, in your question. People shouldn't have to follow a link just to figure out what you're asking about. – Caleb Mar 30 '20 at 15:50

1 Answers1

0

The trick to questions like this one is to find ways to do much less work than the obvious brute-force approach. For each number nums[i] in nums, you're doing nums[i] modulo operations. There are ways that you could cut that number down significantly. When you're trying to speed up code that does the same thing repeatedly, you've got two options: 1) speed up each iteration; 2) reduce the number of iterations needed. If you can't make much headway with one approach, try the other.

Since the point of doing problems like this is to get better at problem solving, I don't think telling you the answer to the problem is the right thing to do. Even so, it's not giving too much away to give an example of what I'm talking about.

Let's say one of the numbers in nums is 24. Right now, your program calculates nums[i]%j for all j from 1 to 24. But you know 1 and nums[i] are always divisors, so once you find that 24 % 2 == 0 and 24 % 3 == 0, you've got four divisors already. By the time you get to 24 % 4 == 0 you've already got 5 divisors, so you know that you can skip 24 because it has more than 4 divisors. Bailing out as soon as you can saves a lot of wasted work.

So, use what you know to reduce the amount of work that your code does. There are several other ways to do that in this problem, and in fact an optimal solution won't even need the explicit check above. Even for large numbers, the number of mod operations needed to check each number will be much smaller than the number itself.

Caleb
  • 124,013
  • 19
  • 183
  • 272