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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
package iqLib.stringLib; public class NumberFactors { public static void PrintFactors(int number) { if (number <= 1) { return; } // Print the first set of factors System.out.println(""+ number + " * 1"); printFactorsHelper("", number, number); } private static void printFactorsHelper(String currExpression, int dividend, int previousFactor) { for (int factor = dividend - 1; factor >= 2; --factor) { if (dividend % factor == 0 && factor <= previousFactor) { // found 2 factors int nextFactor = dividend / factor; // try printing only if secondfactor is smaller (i.e. descending order) if (nextFactor <= factor) { System.out.println(currExpression + factor + " * " + nextFactor); } printFactorsHelper(currExpression + factor + " * ", nextFactor, factor); } } } } |
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
Latest posts by Ajk (see all)
- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017
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.
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
Line 22 check is redundant.
if a >=b and b>=c , then a>=c follows.
That is a very good point 😀
🙂
Thanks a lot for this post, learned a new problem. Keep it up !!