How is this a bad approach?

I was solving Product of Divisors problem and I was runtime error. Let the error issue be kept apart. Someone advised me to go through the Editorial for the practice problem. I was curious to know that what is the issue with my approach of solving the problem (please do not consider the vector implementation for this matter as with approach , I mean to say the algorithm)?

Here is the link for the solution.

Thanks.

That someone was me. And for your kind information, I had advised you regarding the algorithm/approach also, saying that your approach is wrong and then I asked you to read that tutorial and code again. Well, anyways, now you are so much interested to know where your code fails:

  1. First of all you have taken vector and then the maximum value of N can be 500,000 as given in the problem constraints. And the irony of your code is you’re really multiplying all the divisors. So, take the second for loop for example and try to analyze what will happen if N is a large number near 500000 is given as input => OVERFLOW!
  2. Next, I asked you to read the tutorial, why? Because, again modding the value simply by 10000 wont work, you see. What you have done is you’ve calculated the product of divisors and taking %10000.
  3. Then again a silly mistake not printing answers in newline
  4. Think yourself that if the problem would be just to take the divisors and take the product then how easy it would be. There must be something/some trick to go the actual way. And the tutorial teaches you that.

In case you do not still believe me and still think that I am talking rubbish then simply do this, because I see you are very curious to know what is wrong with your code and do not want to learn what I was saying.

So I modified your code to print the div[0] stored in each step:

#include<iostream>
#include<vector>
using namespace std;

int main(void){
    int T, N;
    cin >> T;
    for(int i = 0; i < T; i++) {
        cin >> N;
        vector<int> div;
        for (int j = 2, k = 0; j < N; j++) {
            if(!(N % j))
                div.push_back(j);
        }
        for(int j = 1; j < div.size(); j++) {
            div[0] = div[0] * div[j];
            cout<<div[0]<<endl;
        }
        cout << (div[0] % 10000) << endl;
    }
    return 0;
}

Run this code that I wrote with the testcases=1 and N=499998, and you will get something

6
36
6012
2008008
1001995992
-511181640
941831504
-1177638112
-1987662304
1763734080
-823747776
-2117218176
752842624
2624

So I have proved my point #1 stated above.

3 Likes

I get your point. Thanks for helping me out.

It took you 3 months? :smiley: I’m glad that it was helpful. :slight_smile: Good Luck.