Compute the minimum number of multiplications to evaluate x^n ComputingXPowN.java
public static List<Integer> getMinimumExpression(int n) {
if (n == 1) {
return Arrays.asList(1);
}
LinkedList<ArrayList<Integer>> expLists = new LinkedList<>();
// Constructs the initial list with one node whose value is 1.
expLists.addLast(new ArrayList<Integer>() {
{
add(1);
}
});
while (!expLists.isEmpty()) {
List<Integer> exp = expLists.pop();
// Tries all possible combinations in list exp.
for (int a : exp) {
int sum = a + exp.get(exp.size() - 1);
if (sum > n) {
break; // No possible solution.
}
ArrayList<Integer> newExp = new ArrayList<>(exp);
newExp.add(sum);
if (sum == n) {
return newExp;
}
expLists.addLast(newExp);
}
}
throw new RuntimeException("unknown error");
}
