How is this solution getting accepted?


#1

The solution goes from 1 to sqrt(A) and thus it was determined that our solution is of O(sqrt(A)) complexity. But including our sort function shouldn’t the time complexity become O(nlogn)? Also if it is true shouldn’t O(n) solution be considered correct. Please tell me if I am misunderstanding something.
How does the solution got accepted?
Code:
vector Solution::allFactors(int A) {
int i,j;
vectorans;
i=1;
//int num=A;
while(i<=sqrt(A)){
if(A%i==0){
ans.push_back(i);
if(A/i!=i)
ans.push_back(A/i);
//cout<<A<<"\n";
}
i++;
}
// ans.push_back(A);
sort(ans.begin(),ans.end());
return(ans);
}


#2

the sorting is not of exactly ‘n’ numbers, it is of (number of factors). And if you use a temporary array wouldn’t need to use sort.
O(sqrt(n)) + O(dlog(d)) where d is number of factors.
Even I am not sure if dlog(d) is bound to be less than sqrt(n). but seems so