Finding nearest non-coprime number

Question

Given an array, I need to find the indices of nearest non-coprime number (i.e. GCD(Ai, Aj) > 1 , for any Ai and Aj in the array, i != j ) Example, let the array be

[2 17 4 6 10]

The answer will be

[3 -1 4 3 4] 

I've written this brute force code (which is O(n^2)) using Binary GCD method, which is not very efficient. I'm wondering if there's a faster way to do this. Particularly in O(NlogN)

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Mayur Kulkarni
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        BladeReader in = new BladeReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        GCDPuz solver = new GCDPuz();
        solver.solve(1, in, out);
        out.close();
    }

    static class GCDPuz {
        public static int gcd(int p, int q) {
            if (q == 0) return p;
            if (p == 0) return q;
            // p and q even
            if ((p & 1) == 0 && (q & 1) == 0) return gcd(p >> 1, q >> 1) << 1;
                // p is even, q is odd
            else if ((p & 1) == 0) return gcd(p >> 1, q);
                // p is odd, q is even
            else if ((q & 1) == 0) return gcd(p, q >> 1);
                // p and q odd, p >= q
            else if (p >= q) return gcd((p - q) >> 1, q);
                // p and q odd, p < q
            else return gcd(p, (q - p) >> 1);
        }

        public int coprime(int p, int q) {
            if (p % 2 == 0 && q % 2 == 0) {
                return 2;
            } else if (p == q + 1 || q == p + 1) {
                return 1;
            } else {
                return gcd(p, q);
            }
        }

        public void solve(int testNumber, BladeReader in, PrintWriter out) {
            int size = in.nextInt();
            int[] arr = in.readIntArray(size);
            int[] ans = new int[size];
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == 1) {
                    ans[i] = -1;
                    continue;
                }
                int left = i == 0 ? -1 : findLeft(arr, i);
                int right = i == arr.length - 1 ? -1 : findRight(arr, i);
                int leftDist = left == -1 ? -1 : i - left;
                int rightDist = right == -1 ? -1 : right - i;
                int anss = findNearestIndex(left, leftDist, right, rightDist);
                ans[i] = anss == -1 ? -1 : anss + 1;
            }
            printa(ans, out);
        }

        private void printa(int[] ans, PrintWriter out) {
            StringBuilder sb = new StringBuilder();
            for (int an : ans) {
                sb.append(an).append(" ");
            }
            out.println(sb.toString());
        }

        private int findRight(int[] arr, int i) {
            if (arr[i] == -1) return -1;
            for (int j = i + 1; j < arr.length; j++) {
                if (coprime(arr[i], arr[j]) > 1) return j;
            }
            return -1;
        }

        private int findLeft(int[] arr, int i) {
            if (arr[i] == -1) return -1;
            for (int j = i - 1; j >= 0; j--) {
                if (coprime(arr[i], arr[j]) > 1) return j;
            }
            return -1;
        }

        private int findNearestIndex(int one, int oneDist, int two, int twoDist) {
            if (oneDist == -1 && twoDist == -1) return -1;
            if (oneDist == -1) return two;
            if (twoDist == -1) return one;
            if (oneDist == twoDist) {
                return Math.min(one, two);
            }
            return oneDist < twoDist ? one : two;
        }
    }

    static class BladeReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public BladeReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public int[] readIntArray(int size) {
            int[] array = new int[size];
            for (int i = 0; i < size; i++) {
                array[i] = nextInt();
            }
            return array;
        }
    }
}

Answer 1

If you are willing to get into factorization, one could traverse the list, once from the left, factoring each number, hashing the index of each new prime (with the prime as the key), updating the index of each prime already seen, and, of course, noting the nearest seen prime. Since this traversal would miss the nearest on the right, conduct another traversal from the right to update any nearer shared prime, using the factor lists already saved.

Answer 2

If you know your max value for your numbers and can afford to keep a list of primes, then factoring them may be a better solution for the average/random case. Otherwise, worst case complexity, it's still O(N*N) - think "all of them are primes" for the worst case.

Approach:

• factor them and store a Map<prime, multiplicity>[N] + int closestNeigh[]
• take a factor and O(N) determine for each of them the closest that contain that factor (prefix/sufix sums will be involved)
• eliminate that factor from all the factor maps
• take the next factor. Adjust the closest neighbor index only if new one is closest.

This may bring some "relief" on the line of O(N*<num_distict_factors>), but again if <num_distict_factors> == N (all primes), then it is still O(N*N)