Swap Sort Explanation | Find a duplicate and a missing number
Vložit
- čas přidán 29. 08. 2020
- Patreon Link: / adityaverma
Video Pdf Notes And Code: / 41019482
Playlist Link: • Find missing and dupli...
Problem Description: www.interviewbit.com/problems...
WE WILL BE WRITING CODE FOR THIS IN UPCOMING VIDEOS
Given an unsorted array of size n. Array elements are in the range from 1 to n. One number from set {1, 2, …n} is missing and one number occurs twice in the array. Find these two numbers in order of one space.
Input:[3 1 2 5 3]
Output:[3, 4]
Duplicate = 3, Missing = 4 .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
Please make linked list, backtracking and Graph & Trees (concepts and impt questions) also!
Pls like whoever wants these topics to be covered as well
Algorithm publish nai hota .. banana padta hai : best lines
Bro, it takes a substantial amount of effort to teach from a clean slate and you are doing it very well. I really liked the idea that you don't just jump to the algorithm, rather take the audience along with you to create one.
Love from Canada ❤️
Keep going
aditya bhaiya is like jeetu bhaiya he makes us feel the code also credit to striver too but aditya's explaination is awesome please make more such content
Dude, thanks for doing what you do. You literally saved my ass with your DP and recursion videos!
Best part is : Kaam toh karega hi
Rath ka ma aya or rath tum loge 😂😂
But explanation is too good bhai 🙌 ✨
aditya verma , striver & sumit sir are legends 🔥
You are helping many people with your videos...thanks for doing this...
Hi Aditya!! May I request English subtitles for your videos? You’re probably super busy but I think you channel will be life-changing for people all around the world and reach so many more people with English subtitles. Thank you Aditya!!! (:
This approach is much better than XOR approach, thanks man
Vaiya dp on grid khatam kar do pls....and eagerly waiting for backtracking and graph ...lastly you are the best...❤️❤️
Same
same
yeah pleeeeeeeeeeeeeeeeeeeeeeeeeease
Bhai log koi aur yt me dp on grids aditya bro jaise padhaya hai toh link bhejo 🥲
inka video se kisiko samaj nei ayega, ho i nei sakta hain.. Intuition ko share koi nei karte hain. You are great Aditya
Amazing Explanation Bro, keep doing more algorithms derivation videos. Love it. Thanks
"I hope i made my point clear" & i liked ur video........(thanks bhaiya ji)
Thank you for this approach!
Maza AAgyi boss :D Awesome . PS : He is my Boss from MANIT batch 2020 ;)
Mene coding almost quit kardi thi aur nayi field search kar raha tha, but apki video dekhne ke baad laga ki nahi ek baar fir try karna chiye .bhaut bhaut Thanks apka itna acche se padhane ke liye. You tube pe log atte hai aur code likhna chalu kar dete hai gfg ka solution dekh ke video to me bhi bana lunga but approach impt hai ki esa hi kyu , yehi approach kyu lagi aur ye mujhe aur kahi dekne ko nahi milta. THANKS once again 🙏
Great job Aditya. Make me proud as a MANIT'ian ,from long way back :)
one is aditya from manit and other is sunny verma (2023) batch the chutiya insaan of decade ;)
I am your biggest fan :)
for(int i=0;i
this is 10th time i think
Please complete dp series...
one is aditya from manit and other is sunny verma 2023 batch the chutiya insaan of decade ;)
@@ayushyadav4180 Whos is Sunny Verma?
Bro, please cover more topics. Big fan!
Hmm bhaiya ap sahi bol rahe ho q m kafi algo use hoti unko sirf dry run kr lena is not good kya intuition kya observations h ye kaise kiya jaye .....
Bro To be honest
Dp start majburi me kiya tha par Aab maja aa raha hai
Bro Please come live on youtube once,we subscribers want to meet you
Sure Bro, cant promise anything, but will try ✌️❤️
@Bruno Brian bhai payment ka bhi to option hai uska kya kiya??
🔥🔥
GOAT
We can relate this problem to find the head of the loop in single link list
Please make video on Segment Tree
Thank you for this Aditya!
Please complete the DP playlist whenever you get time.
Me too waiting for that.
Me to
Bro can you please complete stack's last 3 problems??????
It was 11:12 when I got the ans 🥺. And understood what was going to happen. Hint was again the word 'swap'.
Please make vedio on segment tree and graph
Bhaiya subarray problems par bhi playlist bana do plz
Like these problems:
Equilibrium Point
Check if there is a subarray with 0 sun
Longest Sub-Array with Sum K
Longest subarray with sum divisible by K
Largest subarray with equal 1s and 0s
Longest common span with same number of 1s and 0s among two arrays
Find maximum sum in any subarray of size k
Count distinct elements in every window of size k
Check for subarray with given sum
🙌🙌✔
Brother please graph prr bhi videos upload krr do CZcams prr kutch nahi hai graph pdne ke liye aur jo hai wo aap jante ho kaisa hai.
Help me bro please graph pr videos upload krr do.
Bhai Saare concepts ho sake toh ek hi video mein include kar diya karo , bhale hi video lamba ho jaaye , voh better hai ,
Btw nice content , aur Pen copy wale better lagta hai videos aapke short mein zyada samjha dete ho page par , Ussi par shift ho jaao , toh bada sahi lagega bro
Its not a criticism , just a suggestion bro . As always thanks for great content bro
hi again!
bye again 😂
Aagya Aagya Maal Aagya!
After getting the desired array after swap sort -> we got duplicate = 1. So, to find missing number rather than reiterating - we can do like:
missing = sum(ideal_array) - (sum(arr) - duplicate) = sum(1,2,3,4,5) - (sum(1,2,3,1,5)-1) = 15 - (12 - 1) = 4
for case when only 1 is missing and 1 is duplicate, maths method is great .
no need to do what u r telling.
but, if there are multi missing and duplicates, than swap sort is good . .
#include
using namespace std;
int main() {
vector a = {2,3,1,5,1};
int n=5;
int crtPos,dupEle,misEle;
for(int i=0;i
Plzz make the playlist of linked list also (important questions)
understood brother...but this algorithm may not work for negative numbers...is there any alternative to solve....?
Bro why there would be negative number from 1 to n? 😅
yes brother...forgot that point...😅
@@TheAdityaVerma haha
1)bro make more videos and
2)give us more knowledge and .
3)also give us your google pay number too.
or bhai backtracing and greedy kb upload krne ke soche hein pls reply bhai
This channel is awesome 🙂..you can chek other channel "czcams.com/users/Pepcoding" for graph and backtracking ...I like this channel as well.
@@W0807THORE bhai thanks for reply I already follow that channel too
Total case of husband cheating his wife...
Like when sounds are coming from room and wife and wife knocking door from outside😂😂🔥🔥
First 💓
❤️❤️
bro time limit exceed aara hai
Bro when will you teach Kandane's and LIS in DP?
he is actually funny
missing = abs(sum(input_array)-sum(ideal_array));
repeated = sum(input_array)-sum(ideal_array)+missing;
this is more easy may be
0:55 खतम ! टाटा , गुडबाय , गया 😂😂
ना खाऊंगा ना खाने दूंगा।
jo iski sahi jagah pe baitha hai, kya wo wahi hai XD
1=[1,4,3,4,5] from collections import Counter
d=Counter (1)
for i in d:
if d[i]==2: print (1.index (i), i)
bro this code is fine......but the problem statement says that we have to use O(1) space complexity and this code uses O(n) space complexity.
Yeah but tried my best ... And came as a result with this shit😂
If you know another solution please share bro💯
missing = abs(sum(input_array)-sum(ideal_array));
repeated = sum(input_array)-sum(ideal_array)+missing;
this is more easy may be
not working
Python Code -
def missingAndDuplicate(arr):
i = 0
# Put the items at their correct places
while i < len(arr):
if arr[i] != arr[arr[i] - 1]:
# Swap
val = arr[arr[i] - 1]
arr[arr[i] - 1] = arr[i]
arr[i] = val
else:
i += 1
# Now find duplicate and repeated in the array
for i in range(len(arr)):
# If at any index, element is not the correct one, then that element is duplicate and index + 1 is missing element
if arr[i] != i + 1:
print("Duplicate Number ->",arr[i])
print("Missing Number ->", i + 1)
break
why we cant check arr[i]!=(i+1) its going in infinite loop ??
@@rajshah9129 Make sure you swap the positions in the same order as I did. arr[arr[i] -1] must be set first
And then arr[i]
@@DroidHolicOfficial yes i have swap the position in that way only but then too was getting tle if i use arr[I] != (I+1) this condition
And not getting tle if i used arr(I) != arr(arr(I)-1)
Where is jayshree?? 😂😂😂
Spoonfeeding on another level !!!