4
\$\begingroup\$

Write a program in Java that takes a positive integer and prints out all ways to multiply smaller integers that equal the original number, without repeating sets of factors. In other words, if your output contains 4 * 3, you should not print out 3 * 4 again as that would be a repeating set. Note that this is not asking for prime factorization only.

Here is the sample from one solution:

Example:

$ java -cp . PrintFactors 32

32 * 1

16 * 2

8 * 4

8 * 2 * 2

4 * 4 * 2

4 * 2 * 2 * 2

2 * 2 * 2 * 2 * 2

I'm looking for code review, best practices, optimizations etc.

Verifying Complexity: \$O(n!)\$ - time, where \$n\$ is the input number.

public final class PrintFactors {

    private PrintFactors() {}

    public static void printFactors(int number) {
        if (number <= 0) throw new IllegalArgumentException("The number should be greater than 0.");
        printFactorsList(number, number + "*" + 1 + "\n", number);
    }

    private static void printFactorsList(int dividend, String factorString, int prevDivisor) {
        /*
         * This function contains factorString as an argument to facilitate the recursive call for subsequent
         * factors until it reaches prime values. For example, let's say input number = 32 and when i = 8 it prints
         * 8*(32/8) ==> 8 * 4 but the subsequent reduction of 4 is needed and this is done by recursively passing in 4
         * as number. But we also want to maintain the chain "8 * ". So this makes the carry over string as an input
         * argument for the helper function printFactorsList
         */
        for (int divisor = dividend - 1; divisor >= 2; divisor--) {

            if (dividend % divisor != 0)
                continue;

            if (divisor > prevDivisor)
                continue;

            int quotient = dividend / divisor;

            /*
             * 32*1 16*2 8*4 8*2*2 4*4*2 4*2*2*2 2*2*2*2*2
             * 
             * Note: as we go right, the values keeps descending.
             */
            if (quotient <= divisor) {
                if (quotient <= prevDivisor) {
                    System.out.println(factorString + divisor + "*" + quotient);
                }
            }
            printFactorsList(quotient, factorString + divisor + "*", divisor);
        }
    }

    public static void main(String[] args) {
        printFactors(12);
        System.out.println();
        printFactors(32);
    }
}
\$\endgroup\$
3
\$\begingroup\$
public static void printFactors(int number) {
  if (number <= 0) {

You should include the number into the exception's text.

    throw new IllegalArgumentException("The number should be greater than 0.");
  }
  printFactorsList(number, number + "*" + 1 + "\n", number);
}

That's a bad name for a function.

private static void printFactorsList(int dividend, String factorString, int prevDivisor) {

This should be formatted as javadoc.

      /*
       * This function contains factorString as an argument to facilitate the recursive call for subsequent
       * factors until it reaches prime values. For example, let's say input number = 32 and when i = 8 it prints
       * 8*(32/8) ==> 8 * 4 but the subsequent reduction of 4 is needed and this is done by recursively passing in 4
       * as number. But we also want to maintain the chain "8 * ". So this makes the carry over string as an input
       * argument for the helper function printFactorsList
       */

Why not start this loop from prevDivisor? Also, you can optimize this loop by storing numbers in factorized form and generating all divisors less than something on the fly. This will be much faster because you will iterate only over valid divisors. You can also memoize all solutions for a number and reuse them.

  for (int divisor = dividend - 1; divisor >= 2; divisor--) {

    if (dividend % divisor != 0) {
      continue;
    }

    if (divisor > prevDivisor) {
      continue;
    }

    int quotient = dividend / divisor;

          /*
           * 32*1 16*2 8*4 8*2*2 4*4*2 4*2*2*2 2*2*2*2*2
           *
           * Note: as we go right, the values keeps descending.
           */

Merge this two ifs into one.

    if (quotient <= divisor) {
      if (quotient <= prevDivisor) {
        System.out.println(factorString + divisor + "*" + quotient);
      }
    }
    printFactorsList(quotient, factorString + divisor + "*", divisor);
  }
}

public static void main(String[] args) {

You are not reading from anywhere. Is this the intended behavior?

  printFactors(32);
}
\$\endgroup\$
1
\$\begingroup\$

Instead of

    for (int divisor = dividend - 1; divisor >= 2; divisor--)

you could start the loop from Math.min(divisor/2, prevDivisor), which means you execute if (dividend % divisor != 0) about half as often and you don't need to test if (divisor > prevDivisor) at all.

Instead of

        if (quotient <= divisor) {
            if (quotient <= prevDivisor) {

you could just test if (quotient <= divisor). You have already guaranteed that if you get to this step, then divisor <= prevDivisor, so whenever quotient <= divisor it will always be true that quotient <= prevDivisor.

I'm not a fan of continue statements. In this case, I'd put the rest of the body of the loop inside the if statement (which would test if (dividend % divisor == 0), of course).

I'm pretty sure this algorithm is \$O(n!)\$, but I have a strong hunch one could find a much tighter bound on running time. The vast majority of the loops do not call the function recursively; the maximum number of calls directly from a single loop is just the number of proper divisors of dividend.

It might improve running time if the loop iterated over the list of divisors of dividend instead of consecutive integers. The list of divisors is easily generated from the prime factorization, which you can pass into each invocation of the function. (The prime factorization of quotient is just the prime factorization of dividend with its exponents reduced by the exponents of the prime factorization of divisor, so you only really have to factorize the original number before the first call.)

\$\endgroup\$
0
\$\begingroup\$

for (int divisor = dividend - 1; divisor >= 2; divisor--)

In the above for loop, the loop can also be started from (dividend/2), because for all divisors > dividend/2, the Mod will always be <0.

So, starting the loop from dividend/2, might also reduce the runtime.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.