Find missing number in an array

Find missing number in an array

Techdose

4 года назад

124,473 Просмотров

Ссылки и html тэги не поддерживаются


Комментарии:

Shaikh Zaki
Shaikh Zaki - 17.09.2023 11:40

If the array doesn't contain any missing than

Ответить
killer aloo
killer aloo - 14.09.2023 18:57

mast vide thi, sare methods samajh aa gye. Thanq.

Ответить
raju kumar
raju kumar - 05.09.2023 23:35

sir very good explain thankyou sir ji

Ответить
Night Fury
Night Fury - 26.08.2023 11:59

SOLUTION : Here is the solution of all these method in javascript

1) Find Missing Number By Hashing :
const findMissingNumberByHashing = (array: number[]) => {
const hash: Record<string, number> = {};
for (let i = 0; i < array.length; i++) {
hash[array[i]] = 1;
}
for (let i = 1; i <= array.length + 1; i++) {
if (!hash[i]) return i;
}
};

findMissingNumberByHashing([1, 3, 4, 5, 6]);

2) Find Missing Number by Gauss's Method for Summing :
const findMissingNumber = (array: number[]) => {
// (Gauss's Method for Summing)
const n = array.length + 1; // 7 (adding 1 because one number is missing in the array)
const sum = (n * (n + 1)) / 2; // 28
const arraySum = array.reduce((acc, curr) => acc + curr, 0); // 21
return sum - arraySum; // 28 - 21 = 7
};


findMissingNumber([1, 2, 3, 4, 5, 6])

3) Find Missing Number By XOR :
const findMissingNumberByXOR = (array: number[]) => {
let x1 = array[0]; // 1
let x2 = 1; // 1
for (let i = 1; i < array.length; i++) { // in this loop we are calculating the XOR of all the elements of the array
x1 = x1 ^ array[i]; // 1 ^ 3 ^ 4 ^ 5 ^ 6 = 3
}
for (let i = 2; i <= array.length + 1; i++) { // in this loop we are calculating the XOR of all the numbers from 1 to n + 1
x2 = x2 ^ i; // 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 = 1
}
return x1 ^ x2; // 3 ^ 1 = 2
}

findMissingNumberByXOR([1, 3, 4, 5, 6]);

Ответить
GAJ SINGH RATHORE
GAJ SINGH RATHORE - 12.08.2023 23:44

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 <= e) {
int mid = s + (e - s) / 2;

// If the element at index mid is not in its correct position
// i.e., arr[mid] != mid + 1
if (arr[mid] != mid + 1) {
// If arr[mid] is greater than mid + 1 or arr[mid] is negative,
// the missing number is on the left side
if (arr[mid] > mid + 1 || arr[mid] <= 0) {
e = mid - 1;
}
// If arr[mid] is less than mid + 1, the missing number is on the right side
else {
s = mid + 1;
}
}
// If the element is in its correct position, search on the right side
else {
s = mid + 1;
}
}

return s + 1; // The missing number is s + 1

Ответить
Probot143
Probot143 - 10.07.2023 18:24

New 2 Method
1.Match the array position no OR
2.find Even or Odd no

Ответить
Anuj tiwari
Anuj tiwari - 09.07.2023 11:21

can you pls give its source code.. it would be really helpful

Ответить
Ramesh  Daukiya R
Ramesh Daukiya R - 28.03.2023 00:25

code tera baap sikayege kya

Ответить
BK MEHER
BK MEHER - 22.03.2023 22:11

great

Ответить
Aadit Palande
Aadit Palande - 13.02.2023 14:23

Thank you sir , Just one question that how can I build my mind to think for the solution in such various approaches

Ответить
OLD GUARD KILLER
OLD GUARD KILLER - 29.01.2023 11:12

We can Also Use Cyle Sort

Ответить
Nimish
Nimish - 18.01.2023 09:22

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).

Ответить
Iren Jahan 2015
Iren Jahan 2015 - 30.11.2022 15:51

Good video

Ответить
Nikk
Nikk - 23.11.2022 15:25

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

Ответить
Abhishek Rawat
Abhishek Rawat - 20.11.2022 08:47

Yrr 7 8 9 11 12 ke liye work nahi karega :)

Ответить
Kommu Nagasheshu
Kommu Nagasheshu - 13.09.2022 10:27

As well as please explain code for the problem.

Ответить
yaswanth p
yaswanth p - 15.08.2022 17:59

Lovely

Ответить
Waseem Akram Shaikh
Waseem Akram Shaikh - 10.08.2022 08:43

Methode 2 won't work if 0 present in array

Ответить
Vaibhav Jain
Vaibhav Jain - 19.07.2022 23:18

Code for XOR:
//N value=5:
int n;
cin>>n;
//arr=[1,2,3,4]
int arr[n-1],int ans=0;
for(int i=0;i<n-1;i++){
cin>>arr[i];
ans^=arr[i]^(i+1);
}
cout<<ans^n;

Ответить
suhail siddiqui
suhail siddiqui - 07.07.2022 13:36

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<arr.length;i++){
if(arr[i] != i+1){
S.o.p.l(i+1);
break;
}

Ответить
Rohan Kumar Shah
Rohan Kumar Shah - 30.06.2022 10:11

brute better optimal -------> awesome.

Ответить
ANUJ
ANUJ - 25.06.2022 10:44

Sir, kindly explain what is overflow for this case.

Ответить
MAHTAB KHAN
MAHTAB KHAN - 05.06.2022 21:30

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 ?

Ответить
shivam kumar
shivam kumar - 14.05.2022 21:44

From where n=5 comes ??

Ответить
Azealia
Azealia - 21.04.2022 01:25

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

Ответить
MERUGU HARESH
MERUGU HARESH - 17.03.2022 22:43

nice explanation sir

Ответить
dinesh verma
dinesh verma - 11.03.2022 10:10

use binary search, time complexity will be logN

Ответить
Rajan Khunt
Rajan Khunt - 09.02.2022 19:22

GOOD BLOG

Ответить
Niraj Jain
Niraj Jain - 18.01.2022 13:48

Sir can you explain the code for XOR method ??

Ответить
Sanjana Sain
Sanjana Sain - 31.10.2021 18:59

Your voice is same as apna college channel...

Ответить
Gmail Sup
Gmail Sup - 20.10.2021 14:21

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;
}

Ответить
Harpreet Singh
Harpreet Singh - 09.08.2021 15:57

Can you please share the code of the third approach?

Ответить
Suraj Topal
Suraj Topal - 03.08.2021 20:50

XOR one is really cool . I tried with -negative value and array is not sorted still working perfect . Thank a lot sir ji

Ответить
Deepjyoti Debnath
Deepjyoti Debnath - 03.08.2021 12:54

Great video ! 🙌 I understand the XOR operation by this video.

Ответить
Natnael Ghirma
Natnael Ghirma - 02.08.2021 03:15

Sir, what about the time it takes to make the second array(the complete one)?

Ответить
DIT Research Centre
DIT Research Centre - 16.06.2021 14:57

Sort the array then

For(int i=0;i<n;i++)
if(arr[i]!=i+1)
printf("%d",i+1);

Ответить
khushi chaurasia
khushi chaurasia - 12.06.2021 15:17

Your explaining level ....😍😍😍😍

Ответить
abhay manohar saxena
abhay manohar saxena - 05.06.2021 20:42

in second method the n=4 not 5

Ответить
Audio Platform
Audio Platform - 28.05.2021 22:45

nice solution!

Ответить
Praveen perumalsamy
Praveen perumalsamy - 29.04.2021 13:04

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

Ответить
unknow 20
unknow 20 - 18.03.2021 23:53

How to find more then one missing element???

Ответить
Red_APP
Red_APP - 25.02.2021 23:22

find missing number in arere

Ответить
Reena Beeton
Reena Beeton - 11.02.2021 18:39

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

Ответить
Anurag Soni
Anurag Soni - 26.01.2021 18:05

Thanks! for the video

Ответить
Op Choudhary
Op Choudhary - 16.01.2021 10:58

For i=0 to n-1
if(arr[i]!=i+1)
return i+1;

Ответить
Nitin Mahajan
Nitin Mahajan - 05.12.2020 16:37

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.

Ответить
Jatin Ahuja
Jatin Ahuja - 25.10.2020 13:38

Number of terms toh aapne 4 le rkhi hai likha 5 hai

Ответить
Yadhu Nandhan R
Yadhu Nandhan R - 07.10.2020 12:40

If I subtract numbers instead of xor-ing , then will it be as efficient as the xor solution?
i.e for the array 1 2 3 5
(1-1) + (2-2) + (3-3) + (4-5) + (5) = 4

Ответить
Vishal Bhatane
Vishal Bhatane - 04.10.2020 14:40

Thanks

Ответить