Find missing number in an array
ฝัง
- เผยแพร่เมื่อ 25 มิ.ย. 2019
- This video shows three techniques on how to find the missing number in an array. The techniques are based on hashing, sum formula and XOR. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
Great video ! 🙌 I understand the XOR operation by this video.
Thank you sir , Just one question that how can I build my mind to think for the solution in such various approaches
that was just amazing, before this video i was doing like sorting all the element in the array and finding all the element whether if it is at correct index for not
Great video ! 🙌 No need to research the best approach just watch your videos and you are good to go ! Thanks🙌🙌
Welcome :)
@@techdose4u How to find more then one missing element???
@@unknow2096 one simple approach could be, create a set containing (0-n) elements, loop via that list and remove the element from the set. The elements remaining in the set are your missing elements.
mast vide thi, sare methods samajh aa gye. Thanq.
From where n=5 comes ??
note that xor of any number repeats every four digits. so you ca use mod to predetermine the xor of Len(nums). then to find the missing number find the xor of the nums values ONLY. finally return the xor of Len(nums).^ xor of the nums values
Sort the array then
For(int i=0;i
what if the range is random means like 55 to 78
XORing all the elements & then XORing the numbers till n.
And then XORing both tof the obtained results.
This brings us the left out element as XOR of a no with itself is zero(like in binary).
Great explanation 😃
what if there are more than one element is missing in an unsorted array
in case 1,2,3,4,5 how to find? i am getting 0 .
Your explaining level ....😍😍😍😍
:)
For input int[] a = {-1, 1, 2, 3, 4, 5, 6, 7} missing Nums : 18 but it should be '0' can you suggest why I am getting .because as per the algo explain by instructor it should be pass for boundary value also :
public class MissingNumber2 {
private static int missingNumber(int[] input, int n) {
int x1 = input[0];
int x2 = 1;
for (int i = 1; i < n; i++) {
x1 = x1 ^ input[i];
}
for (int i = 2; i
nice explanation sir
If the given array is sorted , then binary search can be applied ( logn) time
Yes you are correct, but only if the array is sorted, while XOR works in all cases :)
what if we sort the array and then start comparing if each element is equal to its index, wherever the condition is a false return that index value.
sorting complexity nlogn we have to do it in N :P
😂
Simply try XOR
Yes
sir very good explain thankyou sir ji
As well as please explain code for the problem.
Can v use binary search after sorting
You can, if you can related your index with array values.
1 and 2 are impratical solution it wont work If negative number is present or missing number not in between. see problem 41 leet code
We can Also Use Cyle Sort
can you pls give its source code.. it would be really helpful
But the third approach will not work of array elements are repeated.
Sir, kindly explain what is overflow for this case.
Overflow occurs when we sum large numbers.
In java integer has some range. If sum goes beyond range, it will cause overflow and doesn't give proper results.
Can you please share the code of the third approach?
int ans1=0,ans2=0;
int j=1;
for(int i=0;i
what if i have multiple missing numbers??
So that will be a totally different question.
Sir, what about the time it takes to make the second array(the complete one)?
You can compute second xor while looping via first array, so it is just O(1* N). You don't really create the second array.
use binary search, time complexity will be logN
What if I do XOR operation between sets in which a={1,2,3} and b={1,2,3,4,5} do i get the answer as {4,5} ???
No. You will get your answer = (4 XOR 5). You won't get 4,5 as individual answers and so you will never know about it. If you have only one number missing and you knew the original array then only you can get your answer as missing element. Here, in your example you have 2 missing numbers and so you won't get the missing elements. I hope you got it :)
Hi, have you ever come across below question?
Given a stream of timestamp and CPU utilisations we need to return the time interval where CPU utilisations was max. Ex input 2d array. [[StartTime, EndTime, cpuUtilization]]
That's the only information I have about the question... What would be your approach to solve this?
Thanks! for the video
Welcome :)
@@techdose4u How to do this questions in swift language.
We can also try subtracting method. if (arr[i] - arr[i-1] == 2) then missing number = arr[i] - 1. Time complexity is O(n) and Space Complexity is O(1).
This wont work for an unsorted array.
tried this but the problem is if the element missing is after the first or before the first place then problem arises
Write a Swift program to check if one of the first 4 elements in a given array of integers is a 7. The length of the array may be less than 4. PLS MAKE VIDEO ON IT
Sir can you explain the code for XOR method ??
int ans1=0,ans2=0;
int j=1;
for(int i=0;i
why u initialized i=2 in second loop
Please mention the time while asking question so as to make it easier to refer.
@@techdose4u in the xor code you provided in the comments
Good video
Thanks
Number of terms toh aapne 4 le rkhi hai likha 5 hai
Very very nice content ❤️
Just sir please us the explanation of pseudo code if you can
Yea I am explaining it from past some time.
TECH DOSE sir you are doing a great Work I haven’t found a channel like you on TH-cam honestly sir very very nice 👍🏻 content and to the point 🔥
TECH DOSE sir plzz add a video on number of pairs in an array it would be great 👍🏻
nice solution!
Thanks
Methode 2 won't work if 0 present in array
Method 2 sum formula not work for all
As if 1, 2,5 now answer must be 3,4 but using tis formula we get 7 wrong
How did the n become 5? is it because it is the biggest?
Isn't this confusing? Array is unsorted. So there is extra complexity to search for largest number. Only then method second can be used.
Also if a sorted array is given , simply missing number is a[i] + 1 where a[i+1] - a[i] != 1
Your voice is same as apna college channel...
What about -ve numbers
[-1, -3] should return 1
then we can use the 2nd method!
n*(n+1)/2 - sum of array elements
Will also work 😄🍻
True. But still O(N) 😁
@@techdose4u in python no issue with integer overflow dude
Is it n because it is the biggest number in the array?
@@JohnLee-xl2ut it's the formula of arithmetic progression , where we are taking 'n' as last term...
@Kartik Bhanderi thanks mate i taught it was always the biggest number. But it is the last number in an array thanks mate :)
2nd method also not work for negative number
The problem statement is supposed to be "Find the missing number form an array containing n distinct numbers in the range [0, n]" , Good one from Tech Dose.
great
XOR one is really cool . I tried with -negative value and array is not sorted still working perfect . Thank a lot sir ji
Hey brother! Can you please share the code, if possible? It'll be very nice of you, if you can.
@@har.preet.singh. sorry brother , you are late. Actually I practice in online compiler we cannot save program .
try yourself brother , if you face any difficulty send your code here then i will help you .
@@surajtopal9940 Here's my python code which isn't working.
def func(N,A):
new=[]
for n in range(max(A)+1):
new.append(-1)
for i in range(N):
if A[i]>=0:
new[A[i]]=True
for j in range(1,max(A)+1):
if new[j]==True:
return j+1
break
L=[]
N=int(input('Enter the number of elements: '))
print('Now, enter the',N, 'elements:')
for n in range(N):
L.append(int(input()))
print(func(N,L))
@@har.preet.singh. brother this is different approach use XOR operation. It is very easy. You just to XOR all the value of the array one by one and put it in the result variable after than you need to do the loop till n and XOR all in the result1 then result ^ result1 and you will get your answer.
Lovely
If the array doesn't contain any missing than
There are lot of numbers in a list
All of them are whole numbers below 100
They are in not any order
Just random whole numbers below 100
We have to find list of numbers which are missing in the series?
Anyone solve it ?
the sum method won't work if there is a zero in the array
The sum technique works for number starting from 1 probably. But for contiguous array, you can use the XOR method which works.
No it works for zero as well. My code got accepted using sum method in leetcode.
can u please share the xor source code
// Function to get the missing number
int getMissingNo(int a[], int n)
{
// For xor of all the elements in array
int x1 = a[0];
// For xor of all the elements from 1 to n+1
int x2 = 1;
for (int i = 1; i < n; i++)
x1 = x1 ^ a[i];
for (int i = 2; i
@@techdose4u why u initialized i =2 in second loop
public static int getMissingNo(int arr[] , int n)
{
int a=1,b=1;
for(int i=0;i
@@vinaykumar-sg7xd because second loop is for XOR elements from 1 to n. x2 is initialized with 1 so if we start with 1 in second loop then it will become 0 in XOR process. so to eliminate that issue, x2 is initialized with 1 and loop started from 2
Can’t we just: 1. initialise counter to array’s zero-th element. 2. Iterate through array increment this counter, wherever the counter and array element does not match - is the answer.
the array may not be in sorted form to be able to have a match with value and it's index probably.
brute better optimal -------> awesome.
GOOD BLOG
in second method the n=4 not 5
How to find more then one missing element???
Try map
@@techdose4u what do you mean
@@unknow2096 you can keep a hashmap to keep track of what all elements you saw. Rest all in the range of 1 to N will be missing.
wont work if there are multiple missing number. Eg.-> i/p- 2 3 1 6 o/p=4.
This example wont work
Numbers are from 1 to n
What if we have multiple numbers missing
Ex - [3,4,5,7,8,10,11]
How to find first missing number?
Please Help
traverse through the array and check the difference between two consecutive numbers
Just use first approach as shown in video.
Xor will not work in this case
I think this one is more efficient, in very few cases you have to iterate over whole array. If array is in order.
for(int i=0;i
The BIG O complexity is still O(N).
Java code: ide.geeksforgeeks.org/6tkkn1JzX0
Yrr 7 8 9 11 12 ke liye work nahi karega :)
New 2 Method
1.Match the array position no OR
2.find Even or Odd no
None of the method will work in case of duplicates method and when numbers are randomly arranged.
This was a simple version where question did not had duplicates.
Then you should add that too.
I mean you must specify it's limitations as you are explaining three methods.
Anyway that's good at all.
Thanks to you.
Sure. I will include other version as well.
find missing number in arere
will help if the array is in order
function missingNum(arr) {
for(i=arr.length-1;i>=0;i--) {
if(arr[i] - arr[i-1] == 2) {
return arr[i]
}
}
return -1;
}
Why you are returning the arr[i] ?this will not give us missing number in array for example 1,2,4 and there is 3 missing number then how we get 3 number by returning the arr[i]
For correct answer we have to return arr[i]-1 rather than returning the a[i]
Your two approach not working.
Ex :- [6,7,8,9]
Your input is wrong
It should contain all the Integers from 1 to n except one missing no
Eg [1,2,3,4,5,7,8,9]
sir code?
Please find it on geeks. I am currently uploading CODE for all new videos.
i found out better approach T.C->O(LOGN) (IF ARRAY IS SORTED) WE CAN USE BINARY SEARCH
int s = 0;
int e = N - 1;
while (s mid + 1 || arr[mid]