Moving chips between cells
I am not convinced that your code works correctly. For example if I run it with the {5,3,15,1,1,3,1} input it will result in 6 what is definietly wrong. (Nothing can have a common divisor with 1 greater than 1).

My other concern is that you only move the chip forward, although it might be necesarry to move it backwards. For example:

{5, 3, 15, 9, 1, 3, 1}


You can get to the 3 on index 5, but only if you step back from the 15 to the 3. Here is the route:

0 -&gt; 2 -&gt; 1 -&gt; 3 -&gt; 5


Your approach is to simulate the optimal route of the chip and the return the result. A cleaner approach would be to calculate all visitable positions and then return the rightmost.

This problem can be naturally interpreted as a graph traversal. The nodes are the cells, and an edge is defined between two nodes if the difference of their indices are at most 2, and they have a common divisor greater then 1.

For this you need a function that finds the greates common divisor. For example:

int gcd(long a, long b) {

    if (b==0)
        return a;
    else
        return gcd(b, a % b);
}


One that tells you if an edge exists between two nodes:

boolean edge(int[] a, int i, int j){
    return gcd(a[i], a[j]) &gt; 1;
}


You need to mark all visited cell using a breath first traversal:

private static boolean[] getVisited(int[] a) {
    boolean[] visited = new boolean[a.length];

    Queue&lt;Integer&gt; toVisit = new LinkedList&lt;Integer&gt;();
    toVisit.add(0);

    while (!toVisit.isEmpty()) {
        int i = toVisit.remove();
        if (visited[i])
            continue;
        visited[i] = true;
        if (i - 2 &gt;= 0 &amp;&amp; !visited[i - 2] &amp;&amp; edge(a, i, i - 2))
            toVisit.add(i - 2);
        if (i - 1 &gt;= 0 &amp;&amp; !visited[i - 1] &amp;&amp; edge(a, i, i - 1))
            toVisit.add(i - 1);
        if (i + 2 &lt; a.length &amp;&amp; !visited[i + 2] &amp;&amp; edge(a, i, i + 2))
            toVisit.add(i + 2);
        if (i + 1 &lt; a.length &amp;&amp; !visited[i + 1] &amp;&amp; edge(a, i, i + 1))
            toVisit.add(i + 1);
    }
    return visited;
}


And then find the rightmost visited cell:

int chipMoving(int[] a) {
    boolean[] visited = getVisited(a);

    for (int i = visited.length - 1; i &gt;= 0; --i)
        if (visited[i])
            return i;

    return 0;
}


The runtime characteristics of finding the visited cells is \$O(N)\$, searching for the rightmost visited is also \$O(N)\$. That makes together \$O(N)\$.