Question

Write a function that takes an array of integers. Every item in the array is in the range 1 ton (inclusively), where n is the size of the array. Some elements appear twice and others appear once. Develop a O(n) algorithm to find all the elements of [1, n] inclusive that do not appear in this array. Your algorithm must be efficient and you may use extra space. Method signature: public static ArrayList find Missing (int [] input) Sample Input/Output: Input Array: 1, 1, 2, 2 Function output: 3, 4 Input Array: 1, 1, 2, 6, 3, 5 Function output: 4 Input Array: 1, 2, 3, 4, 5 Function output: 0

Answer 1

The program code for the question described:

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

import java.util.Scanner;

import java.util.stream.Collectors;

import java.util.stream.IntStream;

public class Test {

public static ArrayList findMissing(int[] input) {

List<Integer> result = IntStream.rangeClosed(1, input.length).boxed().collect(Collectors.toList());

result.removeAll((IntStream.of(input).boxed().collect(Collectors.toList())));

return (ArrayList) result;

}

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

System.out.println("Enter number of elements for the array: ");

int n = scanner.nextInt();

int[] array = new int[n];

System.out.println("Enter elements of the array: ");

for (int i = 0; i < array.length; i++) {

array[i] = Integer.valueOf(scanner.next());

}

System.out.println("Missing elements: ");

System.out.println(Arrays.toString(findMissing(array).toArray()));

}

}

The ouput was:

Enter number of elements for the array:

6

Enter elements of the array:

1 1 2 6 3 5

Missing elements:

[4]