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 <= A <= M and 1 <= B <= N
- \$(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:
Items above the diagonal: (i, j) where 1 <= i < j <= N. Increase the counter by 2 if a valid pair has found. (Symmetric relation)
Diagonal elements.
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;
}