Press "Enter" to skip to content

Print all sets of factors

Ajk 7

Today we will take a look at a problem I personally got asked in an interview! It is called “Print all sets of factors”.
Basically, we will try to write a program that takes an integer as input and print all sets of factors (i.e. all ways to multiply smaller integers that equal the original number), without repeating sets of factors. In other words if our output contains 4*3, then it should not print out 3*4, as it would be a repeating set.

First of all let us try to clarify assumptions. Since the problem itself asks to print we may assume we will just stream out all sets of factors as our solution. The argument will be an integer.

Example runs:

// Print all sets of factors sample run – argument 16
PrintFactors(16)
16 * 1
8 * 2
4 * 4
4 * 2 * 2
2 * 2 * 2 * 2

// Print all sets of factors sample run – argument 32
PrintFactors(32)
32 * 1
16 * 2
8 * 4
8 * 2 * 2
4 * 4 * 2
4 * 2 * 2 * 2
2 * 2 * 2 * 2 * 2

From the above sample runs we can see how it seems like we need the same problem for the biggest factor + concat it to the current factor. To solve this seems like recursion will be the way:

Print all sets of factors – Algorithm

  • Find a factor and print the set with it and the remaining factor
  • Keep current String including the found factor and recurse on the remaining factor

Sound easy no? The terminology can get a bit tricky though. So let us define some terminology.

Print all sets of factors – Terminology

  • number – Initial argument
  • currExpression – The expression in the recursion so far/li>
  • dividend – The current factor in the expression/li>
  • previousFactor – The previous factor in the expression/li>

Note that we need the previousFactor just to keep our newly found factors smaller or equal. This will be our way to make sure we do not repeat tuples when we print all sets of factors. After all this analysis let us get to the coding part.

Let us analyze the time complexity of this solution to “Print all sets of factors”. PrintFactorsHelper itself takes O(n) from the for loop. PrintFactorsHelper will be called at max klog(n) times, since we are always dividing (at least by two) the largest factor, so the resulting complexity should be O(n*log(n)).

Well it took me about 20 mins to write this done, so definitely not a piece of cake, but a moderate difficulty recursive question.

Hope you guys enjoyed it… And I’ll see you guys next time ;D

The following two tabs change content below.
If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media 🙂
  1. Chen Lei Chen Lei

    your code doesn’t include this factor: 12*1 if using PrintFactors(12)

    • Long time, but yes you’re right. We can either print N*1 explicitly, or start the loop at N rather than N-1.

  2. Sreeprasad Govindankutty Sreeprasad Govindankutty

    What is the time complexity of this ?

    • O(n*log(n)). N is the for loop, log(n) is the number of times the helper method gets called. Posted a small analysis

  3. CRH CRH

    Line 22 check is redundant.
    if a >=b and b>=c , then a>=c follows.

      • CRH CRH

        🙂
        Thanks a lot for this post, learned a new problem. Keep it up !!

Leave a Reply

Your email address will not be published. Required fields are marked *