Array Shift algorithm with sample program implementation

Problem. Given an input array of say integers of size n  and a shift factor k ,return an array r, the shifted array by the given factor k.

Constraints

1. The input array can be of size 0 to a very large number e.g. Max Integer Value(214748364)
2. The shift factor can be a very small negative integer i.e. Inter Min Value(-2147483648),0 or a very large positive integer e.g. Max Integer Value(214748364)
3. Handle edge cases.
4. The algorithm should be efficient and fast.

The algorithm

Handling edge cases

1. Given a sample input array {5,3,9,4,2,1} and a shift factor 0, the array remains the same.
2. Given an empty array and any shift factor, the array remains the same

Non edge case processing

1. To get the new positions for each of the array elements, we need to compute the minimum array shift factor because shifting an array elements by 1 is the same as shifting array elements by length+1,(2*length)+1,(3*length)+1,(4*length)+1,….etc. Also shifting array elements by a factor equal to the length of the array is the same as not shifting the array elements at all, i.e. shift factor will be same as shift factor 0 since at last all elements will retain their original positions.
2. To get the new element positions we add their current positions to the minimum required shift factor. If the new position is greater than or equal to the array size, we need to move it to a position from the beginning of the array (index 0) by the computation newPosition-arrayLength. If the shift factor is negative, we are likely to get a new position which is less than the start of the array(index 0).This implies we have to move the new position to a position from the end of the array by the computation newPosition + arrayLength.
3. Once all elements are placed in their new positions, the resultant array is returned.

The below code is implemented in java but will be more or less the same in other programming languages.

package dsa;

 

import java.util.Arrays;

 

public class ArrayShift {

 

    public static void main(String... args) {

 

        int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7};

        int shiftFactor = 12;

        System.out.println("Original Array=" + Arrays.toString(arr));

        System.out.println("Shifted by factor " + shiftFactor + "= " + Arrays.toString(solution(arr, shiftFactor)));

    }

 

    private static int[] solution(int arr[], int factor) {

        if (arr.length == 0 || factor == 0) {

            return arr;

        }

        int len = arr.length;

        int newPos;

        int[] shifted = new int[len];

        factor = factor % len;

 

        System.out.println("Real shift factor:" + factor);

        if (factor == 0) {

            return arr;

        }

        for (int i = 0; i < len; i++) {

            newPos = i + factor;

            if (newPos >= len) {

                newPos = newPos - len;

            }

            if (newPos < 0) {

                newPos = newPos + len;

            }

            shifted[newPos] = arr[i];

        }

        return shifted;

 

    }

}

Output of running the above program

Given the same array and a negative shift factor -9,the output is as below;

If the input array arr is changed to a larger array as below;

int[] arr = new int[]{3, 7, 4, 1, 5, 2, 6, 1, 5, 78, 3, 2, 4, 2, 5, 2, 2, 5, 2, 6, 2, 56, 2, 3, 7, 4, 1, 5, 2, 6, 1, 5, 78, 3, 2, 4, 2, 5, 2, 2, 5, 2, 6, 2, 56, 2, 5, 5, 2, 6, 8, 9, 2, 5, 1, 1, 1, 14, 2, 4, 2, 53, 3};

with a shift factor of 150102 the output is as below

The code used in this example is available on Github.