Hello Again! I was solving a Problem today , Link
and i quickly wrote a brute force / naive solution with a horrible complexity (i thought that before 
)
I was caluclating divisors of number and that too in a recursive function, I seriously didn’t expect it to get accepted. But since it did, now i’m wondering what is the time complexity of my solution. Can someone tell me what’s the time complexity or how come is this fast enough to pass all tests.
My Solution (C++ Code):
#include <bits/stdc++.h>
using namespace std;
vector<int> divisors(int n){
vector<int> res;
for(int i=1;i*i<=n;i++){
int one=i;
if(n%one==0){
res.pb(one);
if(one!=n/one)
res.pb(n/one);
}
}
sort(res.begin(),res.end());
return res;
}
vector<int> solve(int n){
if(n==1){
vi res;
res.push_back(1);
return res;
}
vector<int> temp = divisors(n);
pair<int,int> checker = {0,0};
for(int i=0;i<temp.size()-1;i++){
vector<int> _t = divisors(temp[i]);
if(_t.size()>=checker.first){
checker.first=_t.size();
checker.second=temp[i];
}
}
vector<int> res;
res.push_back(checker.S);
vector<int> next = solve(checker.S);
for(int i = 0 ; i< next.sz ; i++){
res.push_back(next[i]);
}
return res;
}
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(0);
int n;
cin >> n;
vector<int> temp = solve(n);
temp.push_back(n);
set<int,greater<int>> ans(temp.begin(), temp.end());
for(int x:ans){
cout << x << ' ';
}
return 0;
}
