0
\$\begingroup\$

I had an online coding test yesterday. The question is not hard to solve, but I could not achieve the required running time. The question is as follow:

Given \$1 <= M\$, \$N <= 10^5\$ find the count of pairs A, B:

  1. 1 <= A <= M and 1 <= B <= N
  2. \$(A^{1/3} + B^{1/3})^3\$ is an integer Here was my solution:

I notice that this relationship is symmetric, so if assuming M >= N, and imagining we are searching valid points on a M*N matrix, I only need to search the following three parts of the matrix:

  1. Items above the diagonal: (i, j) where 1 <= i < j <= N. Increase the counter by 2 if a valid pair has found. (Symmetric relation)

  2. Diagonal elements.

  3. Items int (i, j) where N+1 <= i <= M, and 1<= j <= N

My java solution is as the following

        static int cubeNumbers(int M, int N) {
            int count = 0;
            if (N > M) {
                int temp = N;
                N = M;
                M = temp;
            }
            for (int i = 1; i <= N; i ++) {
                for (int j = i + 1; j <= N; j ++) {
                    if (isValid(i, j)) {count += 2;}
                }
                if (isValid(i, i)) {count += 1;}
            }
            for (int i = N + 1; i <= M; i ++) {
                for (int j = 1; j <= N; j ++) {
                    if (isValid(i, j)) {count += 1;}
                }
            }
            return count;
        }

        private static boolean isValid(int A, int B) {
            double result = Math.pow(Math.pow(A, 1.0/3) + Math.pow(B, 1.0/3), 3);
            return (result % 1) == 0;
        }
\$\endgroup\$
1
  • \$\begingroup\$ I don't quite follow your logic how you went from the requirements to searching three sections of a matrix. Are you sure that your code gives the correct output in the first place? (even if it takes a long time). \$\endgroup\$ Mar 21, 2016 at 18:36

1 Answer 1

3
\$\begingroup\$

You are going in wrong direction. Entertaining the symmetry doesn't change the quadratic nature of the algorithm (using floating point in a seemingly number-theoretical problem also raises a red flag). The correct approach involves some math.

We are interested in integers \$a,b,n\$ satisfying the relation

$$\sqrt[3]{a} + \sqrt[3]{b} = \sqrt[3]{n}$$

Notice that if \$a\$ and \$b\$ have a common factor, \$n\$ necessarily has the same factor, so we are primarily interested in the solutions with \$a\$ and \$b\$ coprime.

We are going to show that such nontrivial solution is only possible if \$a\$ and \$b\$ are perfect cubes.

Now, \$(\sqrt[3]{a} + \sqrt[3]{b})^3 = n\$. Expanding the binomial gives $$3\sqrt[3]{ab}(\sqrt[3]{a} + \sqrt[3]{b}) = n - (a + b)$$

that is,

$$3\sqrt[3]{nab} = n - (a + b)$$

Since the RHS is obviously integer, so must be LHS. Assuming that \$a\$ is not a perfect cube, it must have some prime factor \$p\$ in a non-cubic power. Further assuming that \$b\$ is coprime to \$a\$, the remaining powers of \$p\$ must be supplied by \$n\$, that is \$n\$ is also divisible by \$p\$.

It means that LHS is divisible by \$p\$, and since \$b = n - a - 3\sqrt[3]{nab}\$, it follows that \$b\$ is also divisible by \$p\$, which contradicts the assumption.

We proved that the set of solutions is comprised by pairs of

$$A = x^3 z, B = y^3 z$$

with \$x, y\$ being coprime integers, and \$z\$ being an arbitrary integer. Enumerating such pairs shall not be a problem.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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