Question

An array A contains n1 unique integers in the range [0,n1] : that is, there is one number from this range that is not in A . Design an O(n) time algorithm for finding that number. You are allowed to use only O(1) additional space besides the array A itself . You may give your algorithm in pseudo-code .

Answer 1

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;


public class Question4883 {


public static Set<Integer> array = new HashSet();

public static void inputNumbers(int n){
& for(int i=1; i<=n; i++)
& array.add(new Integer(i));
}

public static void main(String[] args) {
& // TODO Auto-generated method stub
& BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
& try{
& System.out.println("Enter a number: ");
& int num = Integer.parseInt(br.readLine());
&
& if(num<=0){
& System.out.println("Wrong number!");
& System.exit(0);
& }
& inputNumbers(num);
&
& System.out.println("Enter a search number: ");
& int searchNum = Integer.parseInt(br.readLine());
&
& if((0 < searchNum) && (searchNum <= num)){
& System.out.println("Searching: " + array.contains(Integer.valueOf(searchNum)));
& System.exit(0);
& }
& System.out.println("Wrong number!");
& System.exit(0);
&
& }
& catch(Exception e){
&
& }
}

}