-1
\$\begingroup\$

I would like to know if this is a good solution. This code works but is it efficient enough as i have seen some solutions with \$O(1)\$ time complexity.

    import java.util.Scanner;

public class RotateArray {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int[] arr = new int[n];
        int[] newarr = new int[2 * n];
        for (int i = 0; i < n; i++) {
            arr[i] = s.nextInt();
        }
        System.out.println("original array");
        for (int i = 0; i < n; i++) {
            System.out.println(arr[i]);
        }
        int x = s.nextInt();
        for (int i = 0; i < n; i++) {
            if(i + x < n) {
                newarr[i+x] = arr[i];
            }
            else
                if (i + x >= n) {
                int b = i + x - n;
                newarr[b] = arr[i];
            }
        }
        for (int i = 0; i < n; i++) {
            System.out.println(newarr[i]);
        }
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ You sure its possible to do it in O(1)? Hard to imagine it being better than be better than O(n). \$\endgroup\$
    – bhspencer
    Jan 17 '19 at 16:28
  • \$\begingroup\$ You could use 2 calls to java.lang.System.arraycopy() that would be faster than anything you can write your self. \$\endgroup\$
    – bhspencer
    Jan 17 '19 at 16:33
  • 3
    \$\begingroup\$ Welcome to Code Review! What task does this code accomplish? Please tell us, and also make that the title of the question via edit. Bearing in mind that this post came from SO, please read How to Ask: "State what your code does in your title, not your main concerns about it.". \$\endgroup\$ Jan 17 '19 at 16:42
1
\$\begingroup\$
    for (int i = 0; i < n; i++) {
        if(i + x < n) {
            newarr[i+x] = arr[i];
        }
        else
            if (i + x >= n) {
            int b = i + x - n;
            newarr[b] = arr[i];
        }
    }

This seems rather complicated. Consider

    int rotationPoint = n - x;
    for (int i = 0; i < x; i++) {
        rotated[i] = original[rotationPoint + i];
    }

    for (int i = x; i < n; i++) {
        rotated[i] = original[i - x];
    }

This has fewer lines of code and no if/else structure. It does use two loops instead of one, but it's still shorter. Both loops are also simpler than the original. And they make it clearer that you are doing one thing and then a different thing, not one of two things on any iteration.

I changed the names of the arrays to ones that made more sense to me.

We can actually get this shorter.

    System.arraycopy(original, n - x, rotated, 0, x);
    System.arraycopy(original, 0, rotated, x, n - x);

Now, rather than two loops, we have just two lines of code.

This is still going to be \$\mathcal{O}(n)\$, but it's going to be one of the more efficient linear time implementations. Copying the array is itself a linear time operation, so you won't be able to do better than that so long as you copy the array.

It is possible to rotate without copying. Basically you build a facade over top the array. Something like

class RotatedArray<T> implements Iterable<T> {

    private final T[] original;

    private final int rotation;

    public RotatedArray<T>(T[] original, int rotation) {
        this.original = original;
        this.rotation = rotation;
    }

    private int calculateRotatedIndex(int index) {
        index += rotation;
        if (index >= original.length) {
            index -= original.length;
        }

        return index;
    }

    public T get(int index) {
        return original[calculateRotatedIndex(index)];
    }

    public void set(int index, T datum) {
        original[calculateRotatedIndex(index)] = datum;
    }

    public Iterator<T> iterator() {
       return new Iterator<T>() {

            private int index = 0;

            public boolean hasNext() {
               return original.length > index;
            }

            public T next() {
               return original[calculatedRotatedIndex(index++)];
            }

            public void remove() {
                throw new UnsupportedOperationException(
                        "Cannot remove an element of an array.");
            }

        };
    }

}

The Iterator is modified from the one in this answer. I retained the remove operation, even though it is unnecessary in Java 8 and higher. I modified it to use a generic type and implement the rotation (without testing, so be careful if you try to use it).

I used an if instead of a modulus so that it will handle out of bounds indexes properly. If the array is size ten and the index is thirty, it should throw an exception (and this does). The modulus version would happily change thirty to zero, which is a valid index.

This would be constant time (\$\mathcal{O}(1)\$), as it doesn't copy the array. It's just a facade over the array. But this would actually be slower in many situations, as it has to calculated the rotated index on every array access (read or write). I.e. this is a case where asymptotic analysis is misleading. The particular problem here is that we are calculating the asymptotic behavior of two different kinds of operations: copying the array and accessing the array. Copying the array is always going to be linear time. But accessing the array is constant time.

In this case, each array access is going to be slower. But asymptotically that doesn't matter. They are a constant amount slower, regardless of input size. So the question is if, given all the operations we want to do on the array, it would be faster to copy the array first. In many situations, it will.

\$\endgroup\$
0
\$\begingroup\$

Your newarr doesn't need to be twice the size of arr, since you're already checking if i+x<n.


Also,

else
    if (i + x >= n) {

could just be replaced with else, since the previous condition is if(i + x < n) and it already takes care of the only other possible case.


Now that I think about it, you don't need that whole if/else structure. If you're trying to keep the result smaller than n, modulus will do that for you. if (i+x >= n) { b = i+x-n } could just be replaced with the modulus operator - b = (i+x) % n

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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