**By: Saurav**

**2017-11-11 04:55:00 UTC**

Given a number N, find all factors of N.

Example:

N = 6

factors = {1, 2, 3, 6}

Make sure the returned array is sorted.

This is a simple question where you can just iterate through 1 to that given number and print out those number which divides it. And that does solve the problem.

But in an interview, by asking this question the interviewer wants to see if you can work up a nice efficient solution.

To get started, lets start by writing few tests:

**Attempt 1: **

Lets make it a bit cleaner and remove extra actions taken by one function. So each function does one thing and just one thing best.

**Attempt 2:**

All our tests pass and we have a much efficient solution.

Time complexity: (O(sqrt(n)) + O(k)), where k would be the number of factors

If we add all elements in only one array and then decide to sort it, our complexity will be: (O(sqrt(n)) + O(klogk)) which is greater than what we are using.

In the figure below, I have tried to explain the algorithm I used:

Step 1: Get square root of the number

Step 2: Build two arrays, one stores smaller than the square root and the other stores greater than the square root

Step 3: Iterate though 1 till the (square root+1) and add the perfect divisor and its remainder in smaller and greater array

Step 4: Iterate the greater array in reverse order, adding smaller elements to the smaller array first.

Step 5: Return the uniq of the merged array

Owned & Maintained by Saurav Prakash

If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)