Factor Combinations

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
7 upvotes
Asked in companies
SamsungAppleAmdocs

Problem statement

You are given a positive integer ‘N’. Find all the unique combinations of factors of the given number ‘N’. The product of the factors in each combination should be ‘N’.

You should return a list of combinations of factors. In each combination, factors must be sorted in non-decreasing order. All combinations must be placed in lexicographical order in the list. See the example for more clarity.

Note

1. Factors should be strictly greater than 1 and strictly less than ‘N’.

2. If there is no such possible combination of factors, then return an empty list.

Example:

Consider the positive integer ‘N’ = 12.
Then, we can observe that -:
12 = 2 * 2 * 3
12 = 2 * 6
12 = 3 * 4

i.e,  possible combinations of factors are [2, 2, 3], [2, 6], [3, 4].
Thus, we should return list [[2,2,3], [2,6], [3, 4]].  Note that in this list all combinations are sorted in non-decreasing order, and all the combinations in the list are placed in the lexicographical order.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of test cases. then ‘T’ test cases follow.

The first and the only line of each test case consist of a single integer ‘N’.
Output format : 
For each test case, if there are ‘K’ such possible combinations of factors, then in the first line of the output of the test case print a single integer ‘K’, and then print ‘K’ lines each of them represents a combination of factors of a given integer in non-decreasing order. 

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 50
2 <= N <= 1000

Where ‘T’ is the total number of test cases, and  ‘N’ is the given integer.

Time limit: 1 sec
Sample Input 1:
2
5
12
Sample Output 1:
0
3
2 2 3
2 6
3 4
Explanation of Sample Input 1:
Test case 1:
The integer 5 is a prime number, and it has no factors. Note, we consider that factors should be strictly greater than 1 and strictly less than ‘N’.

Test case 2:
See the problem statement for an explanation.
Sample Input 2:
2
16
4
Sample Output 2:
4
2 2 2 2 
2 2 4 
2 8 
4 4 
1
2 2
Hint

Incrementally find each combination using backtracking.

Approaches (1)
Backtracking

We will make a 2D list of integers ‘result’ to store all the unique factor combinations possible for the given integer ‘N’. We recursively build each of the combinations of the factors in lexicographical order and append them in the list result. 

 

Algorithm

  • Create a 2D list of integers ‘result’.
  • Create a list of integer ‘factors’.
  • Create a recursive function factorCombinationsHelper(curNum, start, factors), where ‘curNum’ be the current integer whose factor greater or equal to ‘start’ needs to be appended in list factors, ‘factors is running a combination of factors of ‘N’. In each recursive call, we’ll do the following-:
    • If curNum = 1, then append list factors in list result and return.
    • Otherwise, Run a loop where ‘i’ ranges from start to N - 1 and in each iteration do the following -:
      • If curNum is divisible by ‘i’, then append ‘i’ in the list factors, then call factorCombinationsHelper(curNum/i, i, factors). After that, we remove the last integer i.e this ‘i’ from list factors, in order to find combinations excluding this one occurrence of factor ‘i’.
  • Return list result by calling this recursive function as factorCombinationsHelper(N, 2, factors).
Time Complexity

O(N ^ (log(N) / 3)), where ‘N’ is the given integer.

 

For integer  ‘N’ the number of its divisors is of the order of cube root of ‘N’ ie O(N ^ ⅓).

It implies that in each recursive step we can have at most N ^ ⅓  further recursive calls.  Also, recursion depth is of the order of log(N) because the maximum size of any required combination of factors of integer ‘N’ can be at most log(N). Thus overall complexity will be O(N ^ (log(N) / 3)).  

Space Complexity

O(log(N)), where ‘N’ is the given integer.

 

The recursion depth is of the order of log(N) because the maximum size of any required combination of factors of integer ‘N’ can be at most log(N). So, the space used by the recursion stack is of the order of log(N). Thus, overall space complexity will be O(log(N)).

Code Solution
(100% EXP penalty)
Factor Combinations
Full screen
Console