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

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

• 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). – Simon Forsberg Mar 21 '16 at 18:36

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{a} + \sqrt{b} = \sqrt{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{a} + \sqrt{b})^3 = n$. Expanding the binomial gives $$3\sqrt{ab}(\sqrt{a} + \sqrt{b}) = n - (a + b)$$

that is,

$$3\sqrt{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{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.