Java

Faultie may count the integers like this: 9; 8; 5; 1; 2. But we were expecting 1; 2; 3; 4; 5; 6; 7; 8; 9; 10 from it. So as you have seen, not only it scrambled the ordering but also forgot quite a few numbers. But one assurance is that Faultie never repeats an integer; it says an integer exactly once. Your task is to write a program that will find out the numbers Faultie has missed and put them in sorted order. So, for the above example, your program should obtain the 1 following sequence: 3; 4; 6; 7; 10. Observe that not only the missing numbers are obtained but also they are put in sorted order. Hint: there is an O(n) algorithm for this problem. Although your algorithm may have a worse time complexity, thinking about a O(n) time algorithm should be fun! No extra points for this though.

>>>>code

package exam1;

public class FixFaulty {

public static int[] findMissingIntegers(int n, int[] faultysOutput) {

int[] answer = new int[n-faultysOutput.length];

/**********************************************/

// Your code goes right here. You may use helper methods if you want to.

// You are not allowed to use any built-in Java data structures such as LinkedList, ArrayList, etc.

// However, you can use arrays, as you did in your previous programming courses.

/**********************************************/

return answer;

}

}

>>>>>test case

package exam1;

import java.util.Arrays;

public class TestFixFaulty {

// Please do not touch this method.

// This method is just trying to match the expected output with the actual output.

public static void match( int[] test, int[] expectedOutput, int[] actualOutput ) {

if( Arrays.equals(expectedOutput, actualOutput ) )

System.out.println("Congratulations! Your code has passed the test: " + Arrays.toString(test) + ". " );

else {

System.out.println("Oops! Your code has failed the test: " + Arrays.toString(test) );

System.out.println("Expected output: " + Arrays.toString(expectedOutput));

System.out.println("Actual output (output from your code): " + Arrays.toString(actualOutput) + " ");

}

}

public static void main(String[] args) {

int n; // Changes with every test input.

////////////////////Test 1////////////////////////////

int[] test1 = {9,8,5,1,2};

n = 10;

int[] expectedOutput1 = {3,4,6,7,10};

int[] actualOutput1 = FixFaulty.findMissingIntegers(n,test1);

match(test1, expectedOutput1, actualOutput1);

////////////////////////////////////////////////

////////////////////Test 2////////////////////////////

int[] test5 = {1,3,5,7,9};

n = 11;

int[] expectedOutput5 = {2,4,6,8,10,11};

int[] actualOutput5 = FixFaulty.findMissingIntegers(n,test5);

match(test5, expectedOutput5, actualOutput5);

////////////////////////////////////////////////

System.out.println("*** Reminder *** for grading, we may use different tests.");

System.out.println("So, use other tests too for testing your code.");

}

}