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.
@@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.
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).
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
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))
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...?
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.
lol what r u talking about just do
for(var i=0; i
i have two solutions:
for(var i=0; i
awesome algorithm.
Thank you so much
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?
Thank you
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.
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.
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..
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;
}
}
}
}
}
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.
will xor work for integers?
Ashitha B yes it works
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.
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
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..
ua-cam.com/video/DEo1Rve-aj8/v-deo.html
@@KnowledgeAmplifier1 lol what about this:
for(var i=0; i
Easy
Method 1 is better
😍😍😍😍😍😍😍😍😍😍😍😍😍😍
explanation is not good
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