Moving chips between cells Challenge:


  You are given a line of N cells with positive integers written in them. Initially a chip is placed on the leftmost cell. Each time it can be moved in any direction (to the left or to the right) on a neighboring cell or across the neighboring cell on the next one. The move is valid if the two numbers - the one the chip is standing on and the one the chip is going to be moved onto - have a common divisor greater than one. How far to the right is it possible to move a chip?


I have a working (I think) method of passing this challenge by recursively checking this method until it finds the optimum solution. I know this is probably the slowest way to do this (\$O(n!)\$?), and it seems that this isn't good enough, because the website I'm submitting my answer to says that I've exceeded my time limit.

Is there any way I can speed up this code?

int chipMoving(int[] a) {

   if(a.length == 1)return 0; //base case
   int b = a[0], c = a[1],d = b;
   while (c!=0){
     int f = c;
     c = b%c;
     b = f;
   }//b is now gcd of a[0] and a[1]

   if(a.length == 2)return b&lt;=1?0:1; //if there are only two terms, return whether we can use the next number one or not 
   int e = a[2];
   while (e!=0){
     int f = e;
     e = d%e;
     d = f;
   }//e is now the gcd of a[0] and a[2]

   int leftMax = chipMoving(Arrays.copyOfRange(a,1,a.length));
   int rightMax = chipMoving(Arrays.copyOfRange(a,2,a.length));

   //if only one is available, use that one
   if(b&gt;1 &amp;&amp; d&lt;=1)return 1+leftMax;
   if(d&gt;1 &amp;&amp; b&lt;=1)return 2+rightMax;

   //check which is better and return that
   if(leftMax &gt; rightMax)return 1+leftMax;
   return 2+rightMax;
}
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)\$.