4
\$\begingroup\$

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<=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>1 && d<=1)return 1+leftMax;
   if(d>1 && b<=1)return 2+rightMax;

   //check which is better and return that
   if(leftMax > rightMax)return 1+leftMax;
   return 2+rightMax;
}
\$\endgroup\$
0

2 Answers 2

2
\$\begingroup\$

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 -> 2 -> 1 -> 3 -> 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]) > 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<Integer> toVisit = new LinkedList<Integer>();
    toVisit.add(0);

    while (!toVisit.isEmpty()) {
        int i = toVisit.remove();
        if (visited[i])
            continue;
        visited[i] = true;
        if (i - 2 >= 0 && !visited[i - 2] && edge(a, i, i - 2))
            toVisit.add(i - 2);
        if (i - 1 >= 0 && !visited[i - 1] && edge(a, i, i - 1))
            toVisit.add(i - 1);
        if (i + 2 < a.length && !visited[i + 2] && edge(a, i, i + 2))
            toVisit.add(i + 2);
        if (i + 1 < a.length && !visited[i + 1] && 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 >= 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)\$.

\$\endgroup\$
1
\$\begingroup\$

To help ensure correctness, it is a good idea to always use braces around your one-line if and loop statements:

if(a.length == 1) { return 0; }

at a minimum, some people would say you should split it into multiple lines:

if(a.length == 1) {
    return 0;
}

You should be consistent with your space around operators; with spaces is easier to read:

while (e!=0){
  int f = e;
  e = d%e;
  d = f;
}

This should be (I used a 4-space indent, 2 spaces is fine, but I prefer 4):

while (e != 0){
    int f = e;
    e = d % e;
    d = f;
}

It is a good idea to use space around arguments too:

chipMoving(Arrays.copyOfRange(a, 1, a.length));

instead of:

chipMoving(Arrays.copyOfRange(a,1,a.length));

Gábor Angyal's answer covers the other aspects of the code very well.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.