Question 3: Given a non sorted array A of size n 2 that contains all the numbers
ID: 3881278 • Letter: Q
Question
Question 3: Given a non sorted array A of size n 2 that contains all the numbers 1 , 2 , 3 , . . . , n except for two. Give an algorithm to find the two missing numbers. Use a constant extra space (namely apart from the array, only a constant number of variables). If this is hard for you use as much space as you want (you will loose some points but not too much).
Example of such array. For n = 13. The next array of 11 elements contains all the numbers from 1 to 13 but 7 and 11: < 12 , 6 , 1 , 8 , 4 , 9 , 12 , 3 , 5 , 13 , 2 > .
Explanation / Answer
I am writing the program in Java programming language. But if you want to change it to some other programming language then you can implement the same. Let me know in the comment's section if you need help in implementing it in some other programming language.
UnsortedArray.java
public class UnsortedArray {
public static void main(String[] args) {
// Unsorted Array
int[] unsortedArray = new int[] {12 , 6 , 1 , 8 , 4 , 7 , 10 , 3 , 5 , 13 , 11 };
// Firstly Sorting the entire array using insertion sort.'
// If you are having trouble understanding below code then please have a look on insertion sort technique.
for(int i=0; i<unsortedArray.length; i++) {
int key = unsortedArray[i];
int j = i-1;
while(j>=0 && unsortedArray[j] > key) {
unsortedArray[j+1] = unsortedArray[j];
j = j-1;
}
unsortedArray[j+1] = key;
}
// Array of size 2 so that we can store the missing values in it
int[] missingElement = new int[2];
// Looping through the Sorted array
for(int i=1; i<unsortedArray.length; i++) {
// Calculating the difference
// Since we know that elements of an array will be from 1 to N expect for two missing elements.
// In the entire array there will be two instances where the difference will be greater than 1.
int difference = unsortedArray[i]-unsortedArray[i-1];
// If the difference is 0 or 1 then both the numbers are same or consecutive numbers
if(difference == 0 || difference == 1) {
// Do nothing
} else {
// Here difference is neither 0 nor 1. That means either of the missing element is encountered
// Checking missingElement[0] because if it is not 0 then we found the second missing number.
// If missingElement[0] is equal to 0 then we found the first missing number.
if(missingElement[0] == 0) {
// Assigning First Missing Number
missingElement[0] = unsortedArray[i]-1;
} else {
// Assigning Second Missing Number
missingElement[1] = unsortedArray[i]-1;
}
}
}
// Printing First Missing Number
System.out.println("First Missing Element is "+missingElement[0]);
// Printing Second Missing Number
System.out.println("Second Missing Element is "+missingElement[1]);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.