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]