Print all factors of a number

Solution:  Print all the factors of a number

void printAllFactors(int num) {
...
}


At first, this appears to be a simple question, but let's start quickly by doing an example to make sure that we understand factors and what is required.  You can't impress an interviewer if you mis-understand something, and sometimes questions are more complicated.


Let's take an example number:  7


In this case, the factors are 1 and 7.


Let's try a more complicated example, 12.  The factors of 12 are:  1, 2, 3, 4, 6 and 12.


Let's think of how we got to 12.  Essentially, we tried dividing 12 by every number up to 12 and found the factors when the remainder was 0.  This is a simple algorithm, but it worked. And,  in an interview, getting a working solution, even a non-optimized one at first, is better than trying for something more complicated from the get go.


So, for a very simple solution:


void printAllFactors(int num) {
    int factorCandidate;


    //We want to test potential factors from 1 to num itself,
    //so slightly different for loop not starting at 0 and
    //going to one less than 1 as is common
    for(factorCandidate = 1; factorCandidate <= num; factorCandidate++) {
        if(num%factorCandidate == 0)
            printf("%d\n", factorCandidate);
    }
}


Well, this works.  It's O(n) as it goes through all numbers less than n.  


But, now, let's say your interviewer asks you, "How can you make this more efficient?"


Let's go through waste in our example to see how we could do better here. 


Let's try the number 12 again.  We tried the factors 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12.


One thing that quickly becomes clear (if not already) is that after we have tested 6, the half way point, no other number will be a factor until the number itself.  Essentially, we don't need to test any number after n/2, and then the number itself will always be a factor


So, a quick optimization is:

void printAllFactors(int num) {
    int factorCandidate;


    for(factorCandidate = 1; factorCandidate <= num/2; factorCandidate++) {
        if(num%factorCandidate == 0)
            printf("%d\n", factorCandidate);
    }
    printf("%d", num);
}


Well, we have increased efficiency by a factor of 2, but now we're told by our interviewer that we can do better.


Let's go back to the number 12, and this time, take a look at the factors, as in pic 1.  One insight in this chart is that factors in this case come in pairs.  So for every factor, there is another factor.

Pic 2 shows the factor pairs of 12.  Essentially, we only need to check for the first half of the factor pair.  And, since the function is not required to print out the factors in order, we can then know the other factor pair with a division problem.  

Now, we just need to go until 'the middle' of the factor pair list as show in pic 2.  This is a number where any other number would be smaller when multiplied to get to num.  Well, there is a special name for this number, the square root.


So, with these insights, we can code up an algorithm to:
- Check numbers up to the square root
- if we find one factor, print out the pair too



void printAllFactors(int num) {
    int factorCandidate;


    for(factorCandidate = 1; factorCandidate <= squrt(num); factorCandidate++) {
        if(num%factorCandidate == 0)
            printf("%d\n%d\n", factorCandidate, num/factorCandidate);
    }
}




Well, this optimization has resulted in O(sqrt(n)), which is a nice reduction.  But, it has a bug.  Can you find the bug?


Hint, look at the output of the number 9.


In this case, we output:
1
9
3
3


Ahh.. The bug is that in this case, we output the 3 twice, when we should only output it once.  This is because 3 is a factor pair of itself, as shown in pic 3.  There is a name for this type of special case, a perfect square.

Now, if we check for this case, we should be all set.



void printAllFactors(int num) {
    int factorCandidate;


    for(factorCandidate = 1; factorCandidate <= squrt(num); factorCandidate++) {
        if(num%factorCandidate == 0) {
            printf("%d\n", factorCandidate);
            // check for perfect square
            if(num/factorCandidate != factorCandidate)
                printf("%d\n", num\factorCandidate);
        }
    }
}



Check some base cases (0, 1, negative numbers), and it looks good.


This is a good example of how a fairly simple problem can become more complex and is common in interviews.  Importantly, get a working solution first, then optimize.  And, when you're looking for optimizations, draw pictures and try to realize what you're doing intuitively.


Please let me know if you know an alternative solution or find a bug.  Thx, Noah