Algorithm that reduces an array of integers to a single value

user_1909123 0
Viewed 292

Given an array of integers.

Inside the for loop, firstly, I'm making a copy of the initial array to a new array. Then the last element is being removed and the rest elements are being rotated by one to the right.

That means the element at index 0 will go to index 1, and so on, and the element will go to index 0.

At this point, I am facing the issue. The previous result has to be a source for the subsequent iteration.

The process continues until there's only one element left in the array.

Here is the code I have:

        int[] arr= {1,2,3,4,5}; // orignal array

        int[] newArr = new int[arr.length];
        int[] result = new int[newArr.length];
        for(int i = 1;i<n;i++)
        {

            newArr = Arrays.copyOf(arr, arr.length - i);
            System.out.println(Arrays.toString(newArr));// here i am deleting one array at last,
// code works fine upto here. but i want the next step as below commented code to perform in loop. which i am really unable to do.

            //System.arraycopy(newArr, 0, result, 1, newArr.length - 1);
            //result[0] = newArr[newArr.length - 1];
            //result = Arrays.copyOf(result,result.length-1);
            //System.out.println(Arrays.toString(result));
        }

output should come like this

[1, 2, 3, 4, 5] // original array

[1, 2, 3, 4] // array after deletion

[4, 1, 2, 3] // array after rotaion

[4, 1, 2]// again after deletion from previous array

[2, 4, 1]// array after rotaion

[2, 4]// again after deletion from previous array

[4, 2]// array after rotation

[4]

final answer is 4
arrays algorithm java
3 Answers

I would not recommend doing everything in a single method. Start by writing a method to perform the rotation. I would name it rotate and it might look something like

private static void rotate(int[] arr) {
    int v = arr[arr.length - 1];
    for (int i = arr.length - 1; i > 0; i--) {
        arr[i] = arr[i - 1];
    }
    arr[0] = v;
}

Then you can use that and a loop to express the algorithm you described

int[] arr = { 1, 2, 3, 4, 5 };
// While there are more than one elements
while (arr.length > 1) {
    // Print the elements
    System.out.println(Arrays.toString(arr));
    // Remove the last element from the array
    arr = Arrays.copyOf(arr, arr.length - 1);
    // Rotate the array
    rotate(arr);
}
// Only one value left
System.out.println(Arrays.toString(arr));

Outputs (as requested)

[1, 2, 3, 4, 5]
[4, 1, 2, 3]
[2, 4, 1]
[4, 2]
[4]
user_29709470

Here is one approach.

int[] arr = {1,2,3,4,5};
while (arr.length > 1) {
    System.out.println(Arrays.toString(arr));
    arr = deleteAndRotate(arr);
}
System.out.println(Arrays.toString(arr));

prints

[1, 2, 3, 4, 5]
[4, 1, 2, 3]
[2, 4, 1]
[4, 2]
[4]
  • return array if length == 1.
  • create a new array of one less size
  • store next to last item in first position
  • fill remainder of new array starting with old.
  • return new array.
public static int[] deleteAndRotate(int[] v) {
    if (v.length == 1) {
        return v;
    }
    int[] r = new int[v.length-1];
    r[0] = v[v.length-2];
    
    System.arraycopy(v, 0, r, 1, v.length-2);
    return r;
}
user_15525340

Your code will perform much better if you get rid of these intermediate arrays. If you have a few million elements in the array, your algorithm will require to allocate in memory a few million arrays which doesn't sound very performance-wise. From the clean-coding point of view, only one defensive copy is needed to preserve the source array intact. And the required operations will be done in place.

The core of this algorithm is the variable len defined inside the method rotateAndDelete(), which denotes the boundary of the "current array".

    public static void main(String[] args) {
        System.out.println(rotateAndDelete(new int[]{1, 2, 3, 4, 5}));
    }

    public static int rotateAndDelete(int[] source) {
        int len = source.length;
        int[] copy = Arrays.copyOf(source, len);
        while (len > 1) {
            len--; // deletion in-place - the last valid index becomes less by one
            rotate(copy, len);
        }
        return copy[0];
    }

    private static void rotate(int[] arr, int len) {
        int first = arr[len - 1];
        // shift all elements to the right
        for (int i = len - 1; i >= 1; i--) {
            arr[i] = arr[i - 1];
        }
        arr[0] = first;
    }

output

4
user_179499450
Related