Factor Combinations

Mark as Completed

Lesson

Given an integer n, write a function to return all possible combinations of its factors (excluding 1 and n). Your function should take in the integer n and return an array of arrays, where each inner array is a possible factor combination of n. The factors should be greater than 1 and less than n.

For example, if we input 16, your function should return [[2, 2, 2, 2], [2, 2, 4], [2, 8], [4, 4]] because these are all possible factor combinations of 16 that are greater than 1 and less than 16.

Walkthrough

To solve this problem, we can use a recursive function to store the factor combinations at each iteration. First, we will create an empty 2D array to store all the possible factor combinations of the input integer n. Then, we will create a helper function called findFactors
which takes in an integer n, a starting index of 2, a current result (an array), and a final result (an array of arrays).In the helper function, we will first check if n is equal to 1. If it is, we will add the current result to the final result (if the current result's length is greater than 1, because we are excluding 1 and n as factors). If n is not equal to 1, we will use a for loop to go through all possible factors (starting from the starting index), and if the factor is divisible by n, we will add it to the current result and call findFactors
again with n divided by the factor as the new n value and the current factor as the new starting index.

Finally, we will push the current result to the final result (if the current result's length is greater than 1) and pop off the last element in the current result before returning the final result.

Here's the code:

function findFactors(n) {
  const finalResult = [];
  findResult(n, 2, [], finalResult);
  return finalResult;
}

function findResult(n, startingIndex, currentResult, finalResult) {
  if (n === 1) {
    if (currentResult.length > 1) {
      finalResult.push(currentResult.slice());
    }
    return;
  }

  for (let i = startingIndex; i <= n; i++) {
    if (n % i === 0) {
      currentResult.push(i);
      findResult(n / i, i, currentResult, finalResult);
      currentResult.pop();
    }
  }

  if (currentResult.length > 1) {
    finalResult.push(currentResult.slice());
  }
}

Big O Complexity Analysis:

The time complexity of this solution is O(n log n) because we are dividing n by each factor that is less than or equal to the square root of n. The space complexity is O(n) because we are storing all possible factor combinations in the final result array. This is a good solution for small values of n, but for larger values of n, it could take a long time to compute all possible factor combinations. However, the constraints of this problem require that the factors be greater than 1 and less than n, which limits the number of possible factor combinations. Therefore, this solution should work well for most inputs.

Previous Lesson Next Lesson