toys/text-manipulation/display-absent-values/README.md

Display Absent Values

This program takes a list of integers in the range [0, 99] in ascending order, and returns a list of the integers in the same range that are not found in the list, also in ascending order. If a single element is not included in the list, it is listed by itself. If a range is not included, then the first and last element of the range are listed, separated by a dash (-). The elements returned are separated by a comma. For example, consider this input:

int[] arr1 = {0, 1, 2, 50, 52, 75};

Calling the program on this array would produce the following result at the prompt:

3-49,51,53-74,76-99

##Assumptions

This method only prints ranges where the gap is two or more elements. If the gap is only a single element, it prints each element. For example, consider this input:

int[] arr2 = {2, 50, 52, 75, 98};

Calling the program on this array would produce the following result at the prompt:

0,1,3-49,51,53-74,76-97,99

Notice, for example, that it does not print 0-1 as the first range.

##Worker Function

The method DisplayAbsentValues() is the method that calculates the elements to include in the output. Here is the program listing for the DisplayAbsentValues() method:

public static String DisplayAbsentValues(int[] input) {
    String result = "";
    int length;
    for (length = 1; length < input.length; ++length) {
        // This breaks out of the loop one pass too early, so increment length afterward
        if (length == input.length - 1 || input[length + 1] == 0) break;
    }
    length++;
    
    ArrayList<Integer> absent = new ArrayList<Integer>();
    for (int ctr = 0; ctr < 100; ++ctr) {
        if (Arrays.binarySearch(input, ctr) < 0) {
            absent.add(ctr);
        }
    }
    for (int ctr = 0; ctr < absent.size(); ++ctr) {
        if ((ctr < (absent.size() - 2)) && (absent.get(ctr + 2) == absent.get(ctr) + 2)) {
            result += absent.get(ctr);
            while ((ctr < (absent.size() - 2)) && (absent.get(ctr + 2) == absent.get(ctr) + 2)) {
                ctr++;
            }
            result += "-" + absent.get(ctr + 1);
            ctr++;
        } else {
            result += absent.get(ctr);
        }
        if (ctr < absent.size() - 1) {
            result += ",";
        }
    }
  return result;
}

##Helper Function

I've included a function PrintArray() that prints the elements of the input array to the console in order to make it easier to compare the input and output. For example, consider the array arr1 above. Calling PrintArray(arr1) would produce the following output:

{0, 1, 2, 50, 52, 75}

Here is the program listing for the function PrintArray():

public static void PrintArray(int[] input) {
    System.out.print("{");
    for (int i = 0; i < input.length; ++i) {
        System.out.print(input[i] + ", ");
    }
    System.out.println("\b\b}");
}

##Driver Function

I've also included a main() method that shows the function DisplayAbsentValues() in operation. There are twelve test cases. It handles the three cases where there is an individual element missing, a range of two elements missing, and a range of more than two elements missing, and it handles those three cases at the beginning, the middle, and the end. It also handles the case where all of the elements included in the input array are separated by ranges of greater than two, and where the first element is at least 3 and the last element is at most 96, thus producing a spanned range before and after each element. Here is the program listing for the main() method:

public static void main(String[] args) {
    System.out.println();
    
    // Array 1
    int[] arr1 = {0, 1, 2, 50, 52, 75};
    PrintArray(arr1);
    System.out.println(DisplayAbsentValues(arr1));
    System.out.println();
    
    // Array 2
    int[] arr2 = {1, 2, 50, 53, 75, 99};
    PrintArray(arr2);
    System.out.println(DisplayAbsentValues(arr2));
    System.out.println();
    
    // Array 3
    int[] arr3 = {2, 50, 52, 75, 98};
    PrintArray(arr3);
    System.out.println(DisplayAbsentValues(arr3));
    System.out.println();
    
    // Array 4
    int[] arr4 = {10, 20, 30, 40, 50};
    PrintArray(arr4);
    System.out.println(DisplayAbsentValues(arr4));
    System.out.println();
    
    // Array 5
    int[] arr5 = {10, 20, 30, 40, 50, 98, 99};
    PrintArray(arr5);
    System.out.println(DisplayAbsentValues(arr5));
    System.out.println();
    
    // Array 6
    int[] arr6 = {10, 20, 30, 40, 50, 97, 99};
    PrintArray(arr6);
    System.out.println(DisplayAbsentValues(arr6));
    System.out.println();
    
    // Array 7
    int[] arr7 = {10, 20, 30, 40, 50, 96, 99};
    PrintArray(arr7);
    System.out.println(DisplayAbsentValues(arr7));
    System.out.println();
    
    // Array 8
    int[] arr8 = {10, 20, 30, 40, 50, 95, 99};
    PrintArray(arr8);
    System.out.println(DisplayAbsentValues(arr8));
    System.out.println();
    
    // Array 9
    int[] arr9 = {0, 1, 10, 20, 30, 40, 50};
    PrintArray(arr9);
    System.out.println(DisplayAbsentValues(arr9));
    System.out.println();
    
    // Array 10
    int[] arr10 = {0, 2, 10, 20, 30, 40, 50};
    PrintArray(arr10);
    System.out.println(DisplayAbsentValues(arr10));
    System.out.println();
    
    // Array 11
    int[] arr11 = {0, 3, 10, 20, 30, 40, 50};
    PrintArray(arr11);
    System.out.println(DisplayAbsentValues(arr11));
    System.out.println();
    
    // Array 12
    int[] arr12 = {0, 4, 10, 20, 30, 40, 50};
    PrintArray(arr12);
    System.out.println(DisplayAbsentValues(arr12));
}