Please code in Java.... and post screenshot of output Design and implement three
ID: 3702356 • Letter: P
Question
Please code in Java.... and post screenshot of output
Design and implement three different algorithms to find a missing number in integer array of 1 to n. The array is not sorted. The missing number could have been replaced by value 0.
Analyze the worse-case complexity (the max number of iteration you need) for each design.
For example, when n is five. The array without missing number should be 1, 2, 3, 4, and 5, but you may see 1, 3, 0, 5, 2 in the array with a missing number. You need to find the missing number, which is 4.
Hint: 1) you can check the number from 1 to n and see which one is missing.
2) you can sort the array and then find the missing number.
3) you can check the sum of all numbers.
Explanation / Answer
Method1: By checking the sum
import java.util.*;
public class Method1 {
public static void main (String[] args) throws java.lang.Exception
{
int n,sum = 0,num;
System.out.print("Enter the limit:");
Scanner sc = new Scanner(System.in);
n= sc.nextInt();
int arr[] =new int[n];
for(int i=0;i<n;i++)
{
arr[i] = sc.nextInt();
}
for(int i=0;i<n;i++)
{
sum =sum+arr[i];
}
num = ((n)*(n+1))/2 - sum;
System.out.print("Missing number is :"+num);
}
}
Method 2: By sorting the array
import java.util.*;
public class Method2 {
public static void main (String[] args) throws java.lang.Exception
{
int n,temp,num;
System.out.print("Enter the limit:");
Scanner sc = new Scanner(System.in);
n= sc.nextInt();
int arr[] =new int[n];
for(int i=0;i<n;i++)
{
arr[i] = sc.nextInt();
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(arr[i]<arr[j]){
temp =arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
int j=1;
for(int i=1;i<n;i++)
{
if(arr[i]!=j)
{
System.out.println("Missing number is :"+j);
return;
}
j++;
}
System.out.println("Missing number is :"+j);
}
}
Method 3: By checking from 1 to n
import java.util.*;
public class Method3 {
public static void main (String[] args) throws java.lang.Exception
{
int n,flag=0;
System.out.print("Enter the limit:");
Scanner sc = new Scanner(System.in);
n= sc.nextInt();
int arr[] =new int[n];
for(int i=0;i<n;i++)
{
arr[i] = sc.nextInt();
}
int i,j;
for(i = 1; i<=n; i++)
{
flag = 0;
for(j=0; j<n; j++)
if(arr[j] == i)
flag = 1;
if(flag == 0)
System.out.println("Missing number is :"+i);;
}
}
}