Logarithmic solution


#1

How about this? Don’t know how to calculate complexity of this but this seems much smaller than logn.
vector Solution::allFactors(int A) {
if (A == 1) return {1};
int low = 1, high = A;
vector out;

for (int i = low; i < high; i++)
    if (A%i == 0){
        out.push_back(i);
        if (i != A/i) out.push_back(A/i);
        high = A/i;
    }
sort(out.begin(), out.end());
return out;

}


#2

It seems I also came up with a more efficient solution thatn discussed in the lesson:

public class Solution {
    public ArrayList<Integer> allFactors(int A) {
        ArrayList<Integer> results = new ArrayList<>();
        results.add(1);
        
        if (A == 1) {
            return results;
        }
        
        results.add(A);
        
        int n = (int) Math.sqrt(A);
        
        while (n > 1) {
            int a = A / n;
            int b = A / a;
            if (A % n == 0) {
                results.add(a);
                if (a != b) {
                    results.add(b);
                }
                n = Math.max(a, b) + 1;
            } else {
                int minAB = Math.min(a, b);
                n = (n != minAB) ? minAB : minAB - 1;
            }
        }

        results.sort(Integer::compare);
        
        return results;
    }
}