We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Factor Combinations

Number: 254

Difficulty: Medium

Paid? Yes

Companies: LinkedIn, TikTok, Uber

Problem Description

Given an integer n, find all possible combinations of its factors where each factor is in the range [2, n - 1]. Each combination’s factors, when multiplied together, should equal n. For example, 12 can be factored as 2 x 6, 3 x 4, and 2 x 2 x 3.

Key Insights

  • We are only interested in factors in the range [2, n - 1].
  • A backtracking/DFS approach can be used to explore possible factor combinations.
  • To maintain an ordered combination and avoid duplicates, start each recursion with the last used factor.
  • When a factor divides n, recursively factorize the quotient starting with that factor.
  • Edge cases: n less than or equal to 1 or prime numbers yield no valid combination.

Space and Time Complexity

Time Complexity: Exponential in the worst-case due to the backtracking nature (practically bounded by the number and size of factors). Space Complexity: O(n) in the worst-case recursion depth, plus additional space for storing combinations.

Solution

We use a depth-first search (DFS) based backtracking approach to build valid factor combinations. At each recursive call, we iterate over potential factors beginning from a given start value. If a factor divides the current value, we include it in the current combination and recursively factorize the quotient. A trick to avoid duplicate combinations is to always pick factors in a non-decreasing order. We also handle the scenario where the quotient itself (if greater than or equal to the current factor) can form a combination.

Code Solutions

def get_factors(n):
    result = []
    
    def dfs(remaining, start, path):
        # If the current path is not empty and remaining itself is a valid factor, add the combination.
        if remaining >= start:
            # To avoid adding the original n as a factor (since we need factors in range [2, n-1])
            if path:
                result.append(path + [remaining])
        # Iterate through potential factors
        factor = start
        # Only iterate up to sqrt(remaining)
        while factor * factor <= remaining:
            # If factor divides remaining, it is a valid candidate
            if remaining % factor == 0:
                dfs(remaining // factor, factor, path + [factor])
            factor += 1

    dfs(n, 2, [])
    return result

# Example usage:
print(get_factors(12))  # Expected output: [[2,6], [2,2,3], [3,4]]
← Back to All Questions