Question #4883

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 .

Expert's answer

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){

&

& }

}

}

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){

&

& }

}

}

## Comments

## Leave a comment