Improving the running time of finding the count of pairs satisfying a symmetric relation

Question

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;
        }

Answer 1

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.