We can solve this problem in log(n). If the array is sorted using binary search arr = list(range(0,79)) + list(range(80,139)) def find_mission(start, end): if start >= end: return start expected = int((start+ end) / 2) if arr[expected] != expected : end = expected else: start = expected + 1 return find_mission(start, end) print(arr) print(find_mission(0, len(arr) - 1))
You can refer to our following articles for the answer: 1. www.geeksforgeeks.org/find-two-missing-numbers-set-1-an-interesting-linear-time-solution/ 2. www.geeksforgeeks.org/find-two-missing-numbers-set-2-xor-based-solution/ The second one discusses the solution using XOR.
Thank you for this video. Could you please tell me if i have to find missing number for list not starting from 1 like [96,100, 99,98] which is 97 how can i use this approach?
sort the array in ascending order. Take its first and last element. Perform any method. If your answer comes 0. Its either 1 less than first or 1 more than last element. For that condition has to be provided.
its mentioned that this problem will be in the range of 1 - n. But if the range changes to 0 - n, use the same method above : In method 1, if u keep subtracting all the elements of the array, you will get 0 as output. In method 2 , use condition statement to check if the number obtained after xoring is 0 or no.
Why can't we just sort the entire list using inbuilt function sort(array,array+size) and then compare the sorted elements of the array with the iteration variable in the for loop if it is not equal then print the missing integer?
We can do that too. The time complexity of that solution will be O(nlogn) as we are sorting the array. However, the XOR technique gives us a time complexity of O(n).
@@spicytuna08 just initialize an array of size n+1 with zero and increment the value of respective index when that number is found in array, at last traverse the array and print the index when a ZERO is encountered.
sir, but this is valid only for 1 to 10, . we just want other then this number . ex- if i enter n=5, 21, 25, 22, 26, 23. and for this our output should be 24, but i am getting -136 . .... why? plz help me out soon
More Simple approach(sort the array athirst, then check if the "I"th element +1 != "I+1"th element, then print the number which is missing.) Code available below -> public class missingNumber { public static void main(String[] args) { int arr[] = {1, 2, 4, 6, 3, 7, 8}; // 1 2 3 4 6 7 8 (5) missing sortArray(arr); getMissing(arr); } private static void getMissing(int[] arr) { int len = arr.length; for(int i=0; i
in the algorithm, u say that in step 2 is take XOR of all n natural number but in code u r taking xor from 2 to n+1, n+1 is fine but why 2 not 0?
dude what is the reason for incrementing the "n"value...?
Geeks for geeks excellent platform to learn
We can solve this problem in log(n). If the array is sorted using binary search
arr = list(range(0,79)) + list(range(80,139))
def find_mission(start, end):
if start >= end:
return start
expected = int((start+ end) / 2)
if arr[expected] != expected :
end = expected
else:
start = expected + 1
return find_mission(start, end)
print(arr)
print(find_mission(0, len(arr) - 1))
what if you need to find 2 missing numbers? how do you do this with XOR?
You can refer to our following articles for the answer:
1. www.geeksforgeeks.org/find-two-missing-numbers-set-1-an-interesting-linear-time-solution/
2. www.geeksforgeeks.org/find-two-missing-numbers-set-2-xor-based-solution/
The second one discusses the solution using XOR.
Indexing from 1 to n. If a(i)!=i means if element value is not equal to index den break the loop and return i value.
How about this??
The list is not sorted. So this wouldn't work.
Thank you for this video. Could you please tell me if i have to find missing number for list not starting from 1 like [96,100, 99,98] which is 97 how can i use this approach?
sort the array in ascending order. Take its first and last element. Perform any method. If your answer comes 0. Its either 1 less than first or 1 more than last element. For that condition has to be provided.
this solution is not working for array containing 0 i.e {3,0,2} giving 6 not 2 why?
lol what r u talking about just do
for(var i=0; i
i have two solutions:
for(var i=0; i
what if there is duplication of elements?
whats the code
pls help me out
In python, We can convert the array into set and then you can apply the mentioned methods.
@@alokyadav6812 no dummy
arr = arr.sort()
for(var i=0; i
How to solve,if i want to find missing number in whole numbers.Printing zero , if zero was missing
its mentioned that this problem will be in the range of 1 - n. But if the range changes to 0 - n, use the same method above : In method 1, if u keep subtracting all the elements of the array, you will get 0 as output.
In method 2 , use condition statement to check if the number obtained after xoring is 0 or no.
Thank you so much
in the second for loop why i is initialized to 2
This is because x2 is initialized as 1. And, we want to take XORs of all the numbers from 1 to n+1. So, we run a loop from 2 to n+1.
Why can't we just sort the entire list using inbuilt function sort(array,array+size) and then compare the sorted elements of the array with the iteration variable in the for loop if it is not equal then print the missing integer?
We can do that too. The time complexity of that solution will be O(nlogn) as we are sorting the array.
However, the XOR technique gives us a time complexity of O(n).
@@GeeksforGeeksVideos Just run a loop from 1 to n and check with i..
we can use hashing tehnique here too,
do you have code? are you thinking about C++ map STL?
@@spicytuna08 just initialize an array of size n+1 with zero and increment the value of respective index when that number is found in array, at last traverse the array and print the index when a ZERO is encountered.
Thank you
awesome algorithm.
will xor work for integers?
Ashitha B yes it works
sir, but this is valid only for 1 to 10, . we just want other then this number . ex- if i enter n=5, 21, 25, 22, 26, 23. and for this our output should be 24, but i am getting -136 . .... why? plz help me out soon
explanation is not good
Entirely wrong
The code works only for the integers from 1 to 9
Even if u use xor method also it's not at all giving the correct answer
Jeedikanti check this , it may work..
czcams.com/video/DEo1Rve-aj8/video.html
@@KnowledgeAmplifier1 lol what about this:
for(var i=0; i
Method 1 is better
public class FIndMissingNumber {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 8, 9, 10, 11};
findNumber(arr);
}
private static void findNumber(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i + 1] - arr[i] != 1) {
System.out.println(arr[i] + 1);
break;
} else if (arr[i + 1] - arr[i] == 1) {
if (i == arr.length - 2) {
System.out.println("Noting is missing");
break;
}
}
}
}
}
Easy
why the hell do you care about complexity when computers are super duper powerful.
when it comes to a large database of an organization, it's important to have a faster and accurate algorithm.
😍😍😍😍😍😍😍😍😍😍😍😍😍😍
More Simple approach(sort the array athirst, then check if the "I"th element +1 != "I+1"th element, then print the number which is missing.) Code available below ->
public class missingNumber {
public static void main(String[] args) {
int arr[] = {1, 2, 4, 6, 3, 7, 8};
// 1 2 3 4 6 7 8 (5) missing
sortArray(arr);
getMissing(arr);
}
private static void getMissing(int[] arr) {
int len = arr.length;
for(int i=0; i