Question 1

Suppose we are given an array, A, of length n such that the indices of the array are from 0 to n 1. You can safely assume that the length of this array is at least 1. This array is further sorted in ascending order but possibly contains duplicates. You are now asked to move the elements around so that all of the values in the original array from index k to n 1 are in ascending order with all duplicates removed. The following figure will make it clear: Figure 1:

In the figure 1, the first array shown in black is passed as input into the function question1 of the class Question1.java. This function mutates the array to make it look like the second array. Notice carefully, that every single value in the second array starting from index k to n 1 are sorted and does not contain any duplicates. The values in the second array starting from 0 to k 1, we do not care. You can have slightly different values in index 0 to index k 1, and that is OK. However, it is important that you have the same values as shown in figure 1, starting from index k to index n 1. In figure 1, k = 4. Here is another example:

Figure 2: In figure 1 and figure 2, notice, that the values in the array from index 0 to index k 1 can be anything, and we call them as Dont Care. Do not worry, if your program gives slightly different values for these indices. What makes this question somewhat challenging is that we ask you to do this writing a single loop. You cannot use any number of nested loops. Here is how you can think about this problem. In the next figure, figure 3, I am providing you with three arrays.

1. The first array is the array that is passed into question1 function of Question1.java. Your program at this moment has not looked at any values in the array starting from index 0 to t. The index k and n 1 are the same. The value in the array from index k to n 1 is just the last item in the array. The last item in the array by itself is already containing no duplicates. Make sure you understand what this means before moving on.

2. The second array is the final state of the array after your question1 returns. At this point you know that every value in the array from index 0 to k 1 represents Dont care and every value in the array from k to n 1 represents No duplicates.

3. But now, let us think of what this array should look like somewhere in between as it progresses from the first array in figure 3 to the second array in figure 3. The third array in figure 3 conveys that everything in the array from index 0 to index t are values remaining to be examined. Notice that t is decrementing, i.e., it is moving to the left. All values in the third array from index t + 1 to index k 1 represents Dont Care. And finally, all values in the third array from index k to index n 1 represents No Duplicates. The third array in figure 3 will approach the array in figure 2 when t is equal to 1

java code to implement:

package hw3; //Make sure to copy/paste the honor code and fill in all the required details. //If you do not complete the honor code, your assignment will not get marked. import java.util.Arrays; public class Question1 { /* * TODO: Complete the function question1 as per the * specifications in the handout. You must only use a single * loop inside the function question1. Do not use any number * of nested loops. In our implementation, our solution is approximately * 15 lines of code. You must call the swap function inside question1. * You cannot use any kind of sorting to answer this question. */ public static void question1(int[] items) { } /* * TODO: You are asked to complete the method * swap. This method takes in as input two ints * and an array of ints. The int i and int j * are the index i and index j in the array items. * You are asked to swap the value at the index i in items * with the value at the index j. You cannot change the function * signature of this method. This method must be called inside question1. */ private static void swap(int i,int j,int[] items) { } /* * Do not write any code inside the main method and expect it to get marked. * Any code that you write inside the main method will be ignored. However, * you are free to edit the main function in any way you like for * your own testing purposes. */ public static void main(String[] args) { //test case 0 int[] items={2,2,4,4,4,5,8,8}; //System.out.println(Arrays.toString(items)); Question1.question1(items); System.out.println(Arrays.toString(items)); //must print [2, 8, 4, 4, 2, 4, 5, 8] System.out.println("--------------------------"); //test case 1 int[] items1={1,2,2,2,2,2,2,2,2}; //System.out.println(Arrays.toString(items1)); Question1.question1(items1); System.out.println(Arrays.toString(items1)); //must print [2, 2, 2, 2, 2, 2, 2, 1, 2] System.out.println("--------------------------"); //test case 2 int[] items2={1,1,1,1,1,1,1,1,1}; //System.out.println(Arrays.toString(items2)); Question1.question1(items2); System.out.println(Arrays.toString(items2)); //must print [1, 1, 1, 1, 1, 1, 1, 1, 1] System.out.println("--------------------------"); //test case 3 int[] items3={1,2,3,4,5,6,7,8,9}; //System.out.println(Arrays.toString(items3)); Question1.question1(items3); System.out.println(Arrays.toString(items3)); //must print [1, 2, 3, 4, 5, 6, 7, 8, 9] System.out.println("--------------------------"); //test case 4 int[] items4={1,2,3,4,5,6,6,7,7,8,8,9,9}; //System.out.println(Arrays.toString(items4)); Question1.question1(items4); System.out.println(Arrays.toString(items4)); //must print [9, 6, 8, 7, 1, 2, 3, 4, 5, 6, 7, 8, 9] System.out.println("--------------------------"); } }