import java.util.Arrays;

public class I1 {
	/**
	 * Moves all elements from index i in a forwards one step. The last element
	 * of the array is no longer in the array. Stores x at index i.
	 * 
	 * Given array of length N, the time complexity is O(N) since it is
	 * necessary to traverse the entire array in the worst case.
	 * Alternatively, one can use more than one variable to say O(N-i) (where
	 * i is the method parameter of the same name), as this more closely
	 * describes the amount of work done.
	 * 
	 * @param a the array in which to insert the value
	 * @param i the index at which to insert the value
	 * @param x the value to be inserted
	 * @throws IllegalArgumentException If array missing or index invalid.
	 * @return the last element in the array
	 */
	public static int insert(int[] a, int i, int x) {
		if( a == null || i<0 || i>=a.length ){
			throw new IllegalArgumentException();
		}

		// save last element
		int last = a[a.length-1];

		// traverse backwards (over destination indices of each copy operation)
		// while copying the elements forwards one step.
		for(int j = a.length-1 ; j >= i+1 ; j--){
			a[j] = a[j-1];
		}

		// insert x
		a[i] = x;

		// return the previously last element
		return last;
	}

	/**
	 * Moves all elements from index i in a forwards one step. The last element
	 * of the array is no longer in the array. Stores x at index i.
	 * 
	 * Given array of length N, the time complexity is O(N) since it is
	 * necessary to traverse the entire array in the worst case.
	 * Alternatively, one can use more than one variable to say O(N-i) (where
	 * i is the method parameter of the same name), as this more closely
	 * describes the amount of work done.
	 * 
	 * @param a the array in which to insert the value
	 * @param i the index at which to insert the value
	 * @param x the value to be inserted
	 * @throws IllegalArgumentException If array missing or index invalid.
	 * @return the last element in the array
	 */
	public static int insert2(int[] a, int i, int x) {
		if( a == null || i<0 || i>=a.length ){
			throw new IllegalArgumentException();
		}

		// save first element to be copied, and write in x instead
		int prev = a[i];
		a[i] = x;

		// traverse forwards over the indices while swapping the element at
		// the index with the saved element.
		for(int j = i+1 ; j <= a.length-1 ; j++){
			int next = a[j];
			a[j] = prev;
			prev = next;
		}

		// return the previously last element
		return prev;
	}

	private static boolean runtest() {
		int[] a = new int[]{4,7,8,2,0};
		if( insert(a, 2, 9) != 0                     )return false;
		if( ! Arrays.equals(a,new int[]{4,7,9,8,2}) )return false;
		if( insert2(a, 1, 3) != 2                     )return false;
		if( ! Arrays.equals(a,new int[]{4,3,7,9,8}) )return false;

		return true;
	}

	public static void main(String[] args) {
		System.out.println("I1: " + (runtest() ? "TEST OK" : "TEST FAILED"));
	}
}