Factor Combinations

Updated on 26 May, 2025
Factor Combinations header image

Problem Statement

Every integer can be represented as a product of its factors. This fundamental concept in number theory not only finds its applications in mathematics but also in computer science, especially in algorithms related to cryptography, prime testing, and more.

Consider a given integer n. Our goal is to find all unique combinations of its factors that multiply to n. These combinations should include only factors that are within the range of [2, n - 1] since 1 and n itself are trivial factors of any number n. The solution should consider all possible sets of factors including repeated uses of the same factor, as long as the product equals n.

For instance, given the number 8, it can be factored as:

  • 8 = 2 x 2 x 2
  • 8 = 2 x 4

The task requires us to return these factor combinations for any input number n in no particular order. If no factors are found that meet the criteria, the output should be an empty list.

Examples

Example 1

Input:

n = 1

Output:

[]

Example 2

Input:

n = 12

Output:

[[2,6],[3,4],[2,2,3]]

Example 3

Input:

n = 37

Output:

[]

Constraints

  • 1 <= n <= 107

Approach and Intuition

When tackling the problem of finding all factor combinations of a number, here's our logical flow and intuition:

  1. Use recursive backtracking to explore possible factors:

    • Start from the smallest possible factor which is 2 and go up to sqrt(n), because a factor larger than sqrt(n) would only pair with a number smaller than sqrt(n) to multiply to n.
    • Use each potential factor to see if it divides n without leaving a remainder, thus ensuring it is indeed a factor.
  2. Whenever a valid factor is found, divide n by this factor and recursively find the factor combinations of the result:

    • If a valid combination is found (product of factors equals n), add the current factor to this combination.
    • Continue this process, treating every intermediate quotient as a new n.
  3. To keep the combinations unique and sorted:

    • Implement the recursive function such that each factor tried is greater than or equal to the last factor included. This avoids repeats in different orders (e.g., [2, 4] and [4, 2]).

Detailed example walkthrough:

For n = 12:

  • Start with the smallest factor, 2. 12/2 = 6. Now find combinations that multiply to 6:
    • Again, start with 2, 6/2 = 3. 3 is also a factor, thus [2, 2, 3] is a valid combination.
    • Next factor could be 3, leading to 3 x 4, hence [3, 4] is a valid combination.
  • The next factor to try for 12 after 2 is 3, which leads directly to 12/3 = 4, and since 4 is valid (because 2 x 2 = 4), [2, 6] is valid.

Given the constraints 1 <= n <= 10^7, the performance of this solution heavily relies on effective pruning of the recursive search space. Efficient handling of recursion depth and memoization (if applicable) to store intermediate results can further optimize the process.

By managing the factors in ascending order and stopping any further recursive calls when a factor is found not to divide n, we can effectively reduce unnecessary computations, leading to more efficient solutions.

Solutions

  • C++
  • Java
cpp
class Solution {
public:
    vector<vector<int>> factorize(int value) {
        vector<vector<int>> results;
        stack<vector<int>> processStack;
        processStack.push({value});
        while (!processStack.empty()) {
            auto current = processStack.top();
            processStack.pop();
            int last = current.back();
            current.pop_back();
            for (int div = current.empty() ? 2 : current.back(); div <= sqrt(last); ++div) {
                if (last % div == 0) {
                    vector<int> newSet = current;
                    newSet.push_back(div);
                    newSet.push_back(last / div);
                    processStack.push(newSet);
                    results.push_back(newSet);
                }
            }
        }
        return results;
    }
};

This summary provides details on how to solve the problem of generating all factor combinations of a given integer using C++.

The provided C++ code defines a class named Solution containing a method factorize which takes an integer value as input and outputs all unique combinations of its factors, excluding 1 and the number itself. This approach uses Depth First Search (DFS) to explore all potential factor combinations effectively.

  • Start by initiating a results vector to store the final sets of factors and a processStack stack to manage the current state during the factorization process.

  • Begin the factorization by pushing the input value onto the processStack.

  • Use a loop to continue processing while there are items in processStack:

    • Retrieve and remove the top element from processStack.
    • If there are previous factors stored in the current combination, use the last factor as the start of the next factor check. Otherwise, start from 2 to avoid duplicates and unnecessary checks.
    • Use a nested loop to check each value from the last factor or 2 up to the square root of the current number (last). This reduces the number of checks needed, leveraging the property that factors are symmetric around the square root.
  • In each iteration of the nested loop, divide the current number (last) by the loop counter (div):

    • If it divides evenly (i.e., last % div == 0), it's a valid factor.
    • Store a new vector newSet that includes the current factors along with div and its complementary factor (last / div).
    • Push newSet onto both processStack for further exploration and results for saving the current set of factors.
  • After exploring all possible combinations, return the results vector which now contains all unique combination sets of factors.

This method ensures a comprehensive search through all potential factor combinations, capturing them efficiently while managing duplicates and unnecessary computations. It's well designed for handling large numbers and can be easily adapted or extended for more complex factorization tasks.

java
class Solution {
    public List<List<Integer>> findFactors(int n) {
        List<List<Integer>> allFactors = new ArrayList<>();
        Stack<ArrayList<Integer>> history = new Stack<>();
        history.push(new ArrayList<>(Arrays.asList(n)));
        while (!history.empty()) {
            ArrayList<Integer> currentFactors = history.pop();
            int currentLast = currentFactors.remove(currentFactors.size() - 1);
            for (int divider = currentFactors.isEmpty() ? 2 : currentFactors.get(currentFactors.size() - 1); divider <= currentLast / divider; ++divider) {
                if (currentLast % divider == 0) {
                    ArrayList<Integer> newFactorList = new ArrayList<>(currentFactors);
                    newFactorList.add(divider);
                    newFactorList.add(currentLast / divider);
                    history.push(newFactorList);
                    allFactors.add(new ArrayList<>(newFactorList));
                }
            }
        }
        return allFactors;
    }
}

This provided Java code defines a method named findFactors which essentially identifies all unique combinations of factors of a given number n that multiply to n. The method implements a depth-first search approach using a Stack data structure for managing the states during iteration. It returns a list of lists, with each sublist representing a valid combination of factors.

Here's a breakdown of the method's operation:

  • An ArrayList named allFactors is initialized to store all possible combinations of factors.
  • A Stack, history, is initialized and is seeded with a list containing the input number n.
  • A while-loop continues until history is empty. Inside the loop:
    • The last list of factors (a combination) is popped from the stack.
    • This combination sans its last element forms the base (currentFactors) for generating new combinations.
  • Iteration begins with either 2 or the last element in currentFactors, going up to the square root of the final element (currentLast) of the popped list.
  • For each number (divider), if it divides currentLast without a remainder, a new combination (newFactorList) is formed which includes divider and the result of the division.
  • This new combination and the running list without the last element but including this new sublist are both pushed back onto the stack.
  • If a valid factor combination is found, it is added to allFactors.
  • The method returns allFactors, which now contains all possible factor combinations for n.

The primary operation is the search for factor combinations using a stack to maintain state and allows backtracking within the factor search space, which efficiently prevents unnecessary recomputation and captures all possible combinations.

Comments

No comments yet.