Note: Please don't use the given array to solve the problem, modifying the input is highly discouraged in an interview. Why? Imagine I give you user data, and ask you to do a task for me using that data, will you modify that data in order to do it? No right, unless I ask you to do so, then only you should.
@@mdrazahassan6315 Big O notation is defined as the upper bound on the run time of the algorithm. If the run time of the algorithm is denoted by f(n), the algorithm is O(g(n)) if c1.g(n)>= f(n) for all n >= n1. So in this case we can take g(n) = n and c1 = 5 and obtain the required result.
I solved in O(N)+O(N log(N)) Time and O(1) space Complexity import java.util.*; public class Find_repeating_missing_numbers { public static void main(String[] arggs){ int[] arr ={4,3,6,2,1,1}; Arrays.sort(arr); int repeat = 0; int missing = 0; int n = arr.length; for(int i=0;i
Hey, I was solving this question on GFG question directed by the link given in Striver's 79 last moment question. But using this solution, only 200/340 TCs passed. Can you please look into it? It will also help other student. Please reply and thankyou so much for creating such excellent content. You really make it easier to learn.
To those whose testcases are failing on gfg and coding ninjas, you need to make sure the 'n' being used in formula is actually in long long format. The 'n' given to us is in 'int' format, so just create a variable 'long long N=n' and then use this 'N' in place of wherever 'n' was used.
@@kipa_chu You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.
I am hear to teach you problem solving. Thats a great saying bother. It actually motivates a lot to look from the point of view of being a great engineer and solving complex problems rather than preparing from interview perspective. Good one
I thought the same idea but as per the question we should not modify 'a' since it's tuple...if we have to then we have convert it to a list...which is taking extra space isn't it...
There would be one more optimal approach.. since the values all could lie between 1 to N including both, and indexes are from 0 to N-1. You can find arr[i] and swap it with arr[arr[i]-1] (since index would be 1 less the value in it), and increment the ptr... thus in any case if you find that arr[i] and arr[arr[i]-1] are equal. then arr[i] is the duplicate element, and then finding duplicate element is easy using both sums(S, Sn). The mentioned two methods were good and cool as well.
BRUTE FORCE: num=[0]*(len(a)+1) for i in range(len(a)): num[a[i]]+=1 for i in range(len(num)): if i==0: continue elif num[i] > 1: P=i elif num[i]==0: Q=i return [P,Q]
Thanks a lot for this amazing content. I would like to share one more approach using modulo operator by placing each number at its correct position==> #include pair missingAndRepeating(vector &arr, int n) {
class Solution: def findTwoElement( self,arr, n): # code here repeat = None i = 0 while i < n: if i is arr[i] - 1 or arr[i] is True: arr[i] = True i += 1 elif arr[arr[i] - 1] is True: repeat = arr[i] i += 1 else: temp = arr[arr[i] - 1] arr[arr[i] - 1] = True arr[i] = temp
for i in range(1, n + 1): if arr[i - 1] is not True: return repeat, i I have done almost the same thing but gettling TLE at 103th test case. The constraint is 10^5 so n should be run faster. but here why am I getting TLE?
Brother my one question to you is that now after the Devin came into the picture, is there the software development will come to the end for the freshers as by the trends and the rise of ai recently makes me think that even after doing ton of dsa don't make our future safe so can we shift to data or cloud, what is your take on it?
Thank you for the great explanation. If you adopt the third approach and forget the formulas for the summation of the n natural numbers and their squares, would it be frowned upon if you summate inside the loop together with the summation of the given input?
Time complexity :- O(nlogn) with the xor method. space complexity :- O(1) Used the property a ^ b = c a = c ^ b logn is for finding the repeating number by having a counter to traverse through the array. class Solution{ public: vector findTwoElement(vector arr, int n) { int x = 0, y = 0; for(int i = 1; i
i think my solution is also optimal Even though i am sorting but still int n = arr.size(); int repeat = 0, miss = 0; sort(arr.begin(), arr.end()); for (int i = 0; i < n; i++) { if (i > 0 && arr[i] == arr[i - 1]) { repeat = arr[i]; } } int total = 0; for (int i = 1; i
Thank you striver for giving us such a wonderful course , but there can be another approach we can do it by using floyds cycle detection technique also .
I tried doing it by the Floyd's cycle detection method, I got a runtime error. For example in this test case, n = 6; arr = {6,5,4,3,4,1}. Slow pointer will by pointing towards i=6 and i is limited to 5. Correct me if I am wrong here.
At the end when we are trying to find which one is repeating and which one is missing instead of traversing the array again we can use this to find the missing one and repeating one.. if(total_sum - ans1 + ans0 == sum)return {ans1,ans0}; return {ans0,ans1}; where total_sum is sum of the values in the grid and "Sum" is sum of first n natural numbers. ThankYou Striver for all these amazing content.
one more approach make them at correct position vector findMissingRepeatingNumbers(vector a) { int n = a.size(); long long sum = 0; int repeat, missing; for (int i = 0; i < a.size(); i++) { sum += a[i]; } int i = 0; while (true) { while(a[i]==i+1) i++; int idx = a[i]; if (a[idx - 1] == a[i]) { repeat = a[idx - 1]; break; } swap(a[idx - 1], a[i]); } missing = (n * 1ll * (n + 1)) / 2 - (sum) + repeat; return {repeat, missing}; }
00:04 Find the repeating and missing number in an array of integers. 02:03 Implementing Brute Force approach for finding missing and repeating numbers 06:23 Optimal solution for finding the missing and repeating number using basic mathematics 08:23 The missing number is 5 and the repeating number is 1. 13:01 Finding the Missing and Repeating Number using equations 15:23 The main equation to find the missing and repeating number is x - y = value 1 and x + y = value 2 19:51 Using the XOR concept to find the missing and repeating numbers. 21:43 The differentiating bit between two different numbers can be found by comparing their binary representations. 25:45 Numbers appearing even number of times are part of the zero club and odd number of times are part of the one club 27:48 The missing number is 5 and the repeating number is 1. 31:29 Find the missing and repeating number using four approaches 33:23 Finding the missing and repeating number using 4 approaches 37:16 The process involves canceling out the numbers using bit manipulation. 39:16 Bit manipulation trick to find a missing number can be written as x and not of x minus one
#Free Education For All.. # Bhishma Pitamah of DSA...You could have earned in lacs by putting it as paid couses on udamey or any other elaerning portals, but you decided to make it free...it requires a greate sacrifice and a feeling of giving back to community, there might be very few peope in world who does this...."विद्या का दान ही सर्वोत्तम दान होता है" Hats Off to you man, Salute from 10+ yrs exp guy from BLR, India.
Below here is another method using Cyclic Sort that takes O(2N) time and O(1) space complexity. class Solution { public: vector findTwoElement(vector arr, int n) { vector ans(2); for(int i=0; i
bro do you have set a deadline to complete the vid solution of DSA course!! If only one vid will be upploaded in a day then also it would take an year to finish DSA course!!! Can u winish the DSA couse till june please please please
Bro, majority of videos are out of advanced topics. You can move ahead and do them. I will not be compromising on quality, even if it takes me sometime. Also, how do you expect someone to upload more than 1 video. A day just has 24 hours FYI.
I tried one more optimal approach where we don't need to Use Square sum. vector findMissingRepeatingNumbers(vector < int > a) { sort(a.begin(),a.end()); int dup=-1; int sum=0; for(int i=0;i=1 && a[i]==a[i-1]) { dup=a[i]; } } int n=a.size();
int sum2=n * (n+1); sum2=sum2/2; int ans=sum2-(sum-dup); return{dup,ans}; }
All good. Just 1 thing I didn't get about the XOR approach - what if there are odd no. of 1's in the given array?? Because in that case, the overall XOR will become 0 for the zero club. Rest understood everything.
Tip : Xor of Natural Numbers can be calculate in O(1) code: lets say you want to do xor of number from 0->n. then ........................................... if (n % 4 == 0) { xor2 = n; } else if (n % 4 == 1) { xor2 = 1; } else if (n % 4 == 2) { xor2 = n + 1; } else if(n % 4 == 3) { xor2 = 0; } ............................................................ xor2 is ans!!!! reason: xor of natural number are periodic in nature and depends on last number n; do upvote if you find this helpfull
bro we can also use cyclic sort so that repeating element goes and occupies the place of missing element, perform another iteration to check which element is not at correct place.
Respected striver had six star profile on code forces then what made him fail to make us understand the algorithm and hard problems as well Amazing quality of teaching us the most amazing apprpach of doing XOR
Whose test case is failing in case of mathematical solution, its because while calculating S2N, the values might get overflowed. So you need to typecast like you were doing while summing up S2. Or you need to define 'n' as long long.
Hi striver I have one idea for this 3rd method but I don't know my intuition is correct are wrong S-Sn =-4 in this eqn u introduce x &y variable (1+2+3+4+5+6)-(4+3+6+2+1+1)it provides 5-1(S-Sn) .X is misssing number so we can store it X=S .Y is repeating number Y=Sn why didn't directly apply this method????
i just got an idea ...its like we know that the array contents will be from 1 to n so if we first sort the given array then the array will be in accending order so ....if we run a loop of 1 to n and if we compare arr[i]==arr[i-1] which are adjcent elements so that means arr[i] is our duplicate so and in the same loop if we find our array sum. then so if we subtract array sum - duplicate then we will remove addition of duplicate element to our array sum ....and then if we subtract sum of n natural numbers or (sum of 1 to n - modified array sum ) then we will got our missing number hence we can return both missing and duplicate .........time complexity -->O(nlogn)+O(n)........space complexity -->O(1)
Can we use a different approach run a loop from 0 to n-1(calculate sum) in each iterartion check if number exists in hash if exists store as repeating number if not add to hashmap after loops is done excecuting we will have repeating number and sum of arr we can calculate sum of n numbers to get the missing number we can just use formula ( (Es(expected Sum of n numbers) - As(array sum)) + repeating number) Time complexity: O(N) Space complexity: O(N)
my solution for this public static List Find(int []arr, int n){ Listlist = new ArrayList(); if(arr[arr.length-1] != arr.length){ list.add(n); } Arrays.sort(arr); for (int i = 0; i
sum of squares method is failing in GFG at some test case here's my code vector findTwoElement(vector arr, int n) { long long N=n; long long Sn= (N*(N+1))/2; long long S2n=(N*(N+1)*((2*N)+1))/6; long long sum=0; long long sum2=0; for(int i=0;i
Note: Please don't use the given array to solve the problem, modifying the input is highly discouraged in an interview.
Why? Imagine I give you user data, and ask you to do a task for me using that data, will you modify that data in order to do it? No right, unless I ask you to do so, then only you should.
Can anyone please explain time complexity for XOR approach . How come it is O(n) when we are running loop for 4 time?
@@mdrazahassan6315 Big O notation is defined as the upper bound on the run time of the algorithm. If the run time of the algorithm is denoted by f(n), the algorithm is O(g(n)) if c1.g(n)>= f(n) for all n >= n1.
So in this case we can take g(n) = n and c1 = 5 and obtain the required result.
@@mdrazahassan6315 Got your answer bro ? If yes do explain here !
I solved in O(N)+O(N log(N)) Time and O(1) space Complexity
import java.util.*;
public class Find_repeating_missing_numbers {
public static void main(String[] arggs){
int[] arr ={4,3,6,2,1,1};
Arrays.sort(arr);
int repeat = 0;
int missing = 0;
int n = arr.length;
for(int i=0;i
Hey, I was solving this question on GFG question directed by the link given in Striver's 79 last moment question. But using this solution, only 200/340 TCs passed. Can you please look into it? It will also help other student. Please reply and thankyou so much for creating such excellent content. You really make it easier to learn.
To those whose testcases are failing on gfg and coding ninjas, you need to make sure the 'n' being used in formula is actually in long long format. The 'n' given to us is in 'int' format, so just create a variable 'long long N=n' and then use this 'N' in place of wherever 'n' was used.
THANKS i submitted 3 time by changing different thing but 1 test case failed everytime....thanku so much for saving my time
thanks a lot😄
Can you share your code i have tried everything and it still fails.
thanks
Tqsm
Same question @leetcode : *Set Mismatch* 🙂🙂
No its different. The input limit is not 1 to N
@@kipa_chu it is
@@kipa_chu You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.
I am hear to teach you problem solving. Thats a great saying bother. It actually motivates a lot to look from the point of view of being a great engineer and solving complex problems rather than preparing from interview perspective. Good one
understood, will come back later to understand the last approach :)
Bro , usually I don't do comments in any videos ..but this video's forces me to do...top notch content , understood all the 4 algorithm!!❤🎉
Hy sir as you already know that our summer holidays are started, so I request you to please increase the frequency of upload 🙏🙏
Hey I found one more optimal approach in O(n). This also uses some maths
int n = a.size();
int sum = 0;
int p;
for(int i=0; i
what is abs here ? vector abs; ??
@@vrajpatel9259 it's absolute value fn returns always the positive number as output
I thought the same idea but as per the question we should not modify 'a' since it's tuple...if we have to then we have convert it to a list...which is taking extra space isn't it...
This problem is available on leetcode with name "Set Mismatch". Thoda story based question hai but exactly same hai😊
16:54 bro encountered the greatest problem in entire computer science
striver bhaiya without you i cant able to understant nothing in dsa thanku for all of you videos
I saw differnt youtubers doing a negation method by mofying the given array which is so wrong just loved this explanation by striver bhaiya 🔥🔥❤❤
There would be one more optimal approach.. since the values all could lie between 1 to N including both, and indexes are from 0 to N-1. You can find arr[i] and swap it with arr[arr[i]-1] (since index would be 1 less the value in it), and increment the ptr... thus in any case if you find that arr[i] and arr[arr[i]-1] are equal. then arr[i] is the duplicate element, and then finding duplicate element is easy using both sums(S, Sn). The mentioned two methods were good and cool as well.
God of coding learners..❤
Hey striver lots of love and support for u ❤❤ u r doing such a great great work for us thanks a lottttt.......it means a lot
Bro, I noticed that majority of the array question in the medium and hard part optimization involves hashing. Like 70%..
Yes because hashing helps to calculate the number of occurences
thanks for the mind blowing final optimal approach
last approach just blown my mind.
BRUTE FORCE:
num=[0]*(len(a)+1)
for i in range(len(a)):
num[a[i]]+=1
for i in range(len(num)):
if i==0:
continue
elif num[i] > 1:
P=i
elif num[i]==0:
Q=i
return [P,Q]
Master blaster ❤ your explanation is very clear and we understand it very well ❤ thank you for such efforts 🙏
Absolutely amazing sir!! thank you very much!! Just to know, when will you start teaching linked list, stacks, queue ??
2nd approach was amazing man, brilliant
Thanks a lot for this amazing content. I would like to share one more approach using modulo operator by placing each number at its correct position==>
#include
pair missingAndRepeating(vector &arr, int n)
{
int i=0;
while(i
class Solution:
def findTwoElement( self,arr, n):
# code here
repeat = None
i = 0
while i < n:
if i is arr[i] - 1 or arr[i] is True:
arr[i] = True
i += 1
elif arr[arr[i] - 1] is True:
repeat = arr[i]
i += 1
else:
temp = arr[arr[i] - 1]
arr[arr[i] - 1] = True
arr[i] = temp
for i in range(1, n + 1):
if arr[i - 1] is not True: return repeat, i
I have done almost the same thing but gettling TLE at 103th test case. The constraint is 10^5 so n should be run faster. but here why am I getting TLE?
My submission has been accepted I just changed the 'is' to '==' and voila! cause is takes a lot time than '==' cuase of its type checking etc
Brother my one question to you is that now after the Devin came into the picture, is there the software development will come to the end for the freshers as by the trends and the rise of ai recently makes me think that even after doing ton of dsa don't make our future safe so can we shift to data or cloud, what is your take on it?
Thank you for the great explanation. If you adopt the third approach and forget the formulas for the summation of the n natural numbers and their squares, would it be frowned upon if you summate inside the loop together with the summation of the given input?
You can no issue
@@takeUforward Thank you.
Awesome explanation...Understood all the approaches
the last approach is mind blowing
Time complexity :- O(nlogn) with the xor method.
space complexity :- O(1)
Used the property
a ^ b = c
a = c ^ b
logn is for finding the repeating number by having a counter to traverse through the array.
class Solution{
public:
vector findTwoElement(vector arr, int n) {
int x = 0, y = 0;
for(int i = 1; i
you could have avoided that extra for loop, and used the first one only for the calculation of repeating
i think my solution is also optimal Even though i am sorting
but still
int n = arr.size();
int repeat = 0, miss = 0;
sort(arr.begin(), arr.end());
for (int i = 0; i < n; i++) {
if (i > 0 && arr[i] == arr[i - 1]) {
repeat = arr[i]; }
}
int total = 0;
for (int i = 1; i
It's not optimal.
T.c - O(nlogn)
S.c - O(login) of sorting
Because of YOU I understood the XOR method very easily
Thanks Striver Bhaiyya
Great explanation! 🙂
amazing video explanation ❤❤❤❤❤❤
Blowned Up!!!!
can we use cyclic sort to solve this
Hii bhaiya! Great solution.
why can't we use hare-tortoise to find the repeating number and then maths to find the missing number.
Thank you striver for giving us such a wonderful course , but there can be another approach we can do it by using floyds cycle detection technique also .
Bro third approach sa TLE arha hai gfg pa??
@@himanshukaushik9223 yes mera ara h
I tried doing it by the Floyd's cycle detection method, I got a runtime error. For example in this test case, n = 6; arr = {6,5,4,3,4,1}. Slow pointer will by pointing towards i=6 and i is limited to 5. Correct me if I am wrong here.
Vari mari thala..❤🎉
At the end when we are trying to find which one is repeating and which one is missing instead of traversing the array again we can use this to find the missing one and repeating one..
if(total_sum - ans1 + ans0 == sum)return {ans1,ans0};
return {ans0,ans1};
where total_sum is sum of the values in the grid and "Sum" is sum of first n natural numbers.
ThankYou Striver for all these amazing content.
one more approach make them at correct position
vector findMissingRepeatingNumbers(vector a)
{
int n = a.size();
long long sum = 0;
int repeat, missing;
for (int i = 0; i < a.size(); i++)
{
sum += a[i];
}
int i = 0;
while (true)
{
while(a[i]==i+1) i++;
int idx = a[i];
if (a[idx - 1] == a[i])
{
repeat = a[idx - 1];
break;
}
swap(a[idx - 1], a[i]);
}
missing = (n * 1ll * (n + 1)) / 2 - (sum) + repeat;
return {repeat, missing};
}
Understood Thanks Sir!
00:04 Find the repeating and missing number in an array of integers.
02:03 Implementing Brute Force approach for finding missing and repeating numbers
06:23 Optimal solution for finding the missing and repeating number using basic mathematics
08:23 The missing number is 5 and the repeating number is 1.
13:01 Finding the Missing and Repeating Number using equations
15:23 The main equation to find the missing and repeating number is x - y = value 1 and x + y = value 2
19:51 Using the XOR concept to find the missing and repeating numbers.
21:43 The differentiating bit between two different numbers can be found by comparing their binary representations.
25:45 Numbers appearing even number of times are part of the zero club and odd number of times are part of the one club
27:48 The missing number is 5 and the repeating number is 1.
31:29 Find the missing and repeating number using four approaches
33:23 Finding the missing and repeating number using 4 approaches
37:16 The process involves canceling out the numbers using bit manipulation.
39:16 Bit manipulation trick to find a missing number can be written as x and not of x minus one
Awesome explantion 😍
#Free Education For All.. # Bhishma Pitamah of DSA...You could have earned in lacs by putting it as paid couses on udamey or any other elaerning portals, but you decided to make it free...it requires a greate sacrifice and a feeling of giving back to community, there might be very few peope in world who does this...."विद्या का दान ही सर्वोत्तम दान होता है" Hats Off to you man, Salute from 10+ yrs exp guy from BLR, India.
superb explanation last one
Below here is another method using Cyclic Sort that takes O(2N) time and O(1) space complexity.
class Solution {
public:
vector findTwoElement(vector arr, int n) {
vector ans(2);
for(int i=0; i
Why are you swapping? What's the intuition behind this?
Last approach was really intersting ..
THe XOR method it tough to understand but the method is really helpful to understand the bit concept. And a very optimal approach.
bro do you have set a deadline to complete the vid solution of DSA course!! If only one vid will be upploaded in a day then also it would take an year to finish DSA course!!! Can u winish the DSA couse till june please please please
Bro, majority of videos are out of advanced topics. You can move ahead and do them.
I will not be compromising on quality, even if it takes me sometime.
Also, how do you expect someone to upload more than 1 video. A day just has 24 hours FYI.
I tried one more optimal approach where we don't need to Use Square sum.
vector findMissingRepeatingNumbers(vector < int > a) {
sort(a.begin(),a.end());
int dup=-1;
int sum=0;
for(int i=0;i=1 && a[i]==a[i-1])
{
dup=a[i];
}
}
int n=a.size();
int sum2=n * (n+1);
sum2=sum2/2;
int ans=sum2-(sum-dup);
return{dup,ans};
}
Sorting takes O(nlogn). So your solution even though it doesn't do square sum is inferior
Wonderful explanation!
thanks striver sir for this much explanation.
will visit it again for xor solution
UNDERSTOOD 🎇✨
All good. Just 1 thing I didn't get about the XOR approach - what if there are odd no. of 1's in the given array?? Because in that case, the overall XOR will become 0 for the zero club. Rest understood everything.
Understood✅🔥🔥
understood sir
Done on 9 Jan 2025 at 11:11
Place : Study Room 2 , Hostel 5 IIT Bombay
dob , place of birth bhi batadete
those who are getting floating point error, just make sure val1 is not 0. if it is 0 then return {0, 0}
Tip : Xor of Natural Numbers can be calculate in O(1)
code:
lets say you want to do xor of number from 0->n.
then
...........................................
if (n % 4 == 0)
{
xor2 = n;
}
else if (n % 4 == 1)
{
xor2 = 1;
}
else if (n % 4 == 2)
{
xor2 = n + 1;
}
else if(n % 4 == 3)
{
xor2 = 0;
}
............................................................
xor2 is ans!!!!
reason: xor of natural number are periodic in nature and depends on last number n;
do upvote if you find this helpfull
Understood, thank you.
Understood 🔥
Understood 🎉
19:17 sir jab aapne x and y ki type casting long long se kri hai toh return krte vakt int int kyu laga diya?
We need to return int values.
We can also type cast at assigning of x and y
Like:
int x=(int) ( (val1 + val2)/2) ;
Nice🤗
understood 👍👍
bro we can also use cyclic sort so that repeating element goes and occupies the place of missing element, perform another iteration to check which element is not at correct place.
Respected striver had six star profile on code forces then what made him fail to make us understand the algorithm and hard problems as well
Amazing quality of teaching us the most amazing apprpach of doing XOR
Whose test case is failing in case of mathematical solution, its because while calculating S2N, the values might get overflowed. So you need to typecast like you were doing while summing up S2. Or you need to define 'n' as long long.
Hi striver I have one idea for this 3rd method but I don't know my intuition is correct are wrong
S-Sn =-4 in this eqn u introduce x &y variable (1+2+3+4+5+6)-(4+3+6+2+1+1)it provides 5-1(S-Sn) .X is misssing number so we can store it X=S .Y is repeating number Y=Sn why didn't directly apply this method????
hey striver do you have any plans to make videos on OOPs? there is no good playlist that teaches OOPs from beginner to advanced.
Yes lets do it soon 💯
@@takeUforward waiting for more DSA stuff
Thankyou sir!
Thank you!!
I am not feeling well, so I timestamped it 1 day later.
00:20 Problem Statement
01:14 Brute Force approach
02:08 Pseudocode
03:18 Complexity
03:47 Better approach (Hashing)
05:41 Code
06:58 Complexity
07:28 Optimal approach (Maths + XOR)
08:01 Solution-01 (Maths)
08:08 Intuition + Approach
14:54 Code
19:17 Complexity
19:55 Solution-02 (XOR)
20:15 Intuition + Approach
31:11 Code
41:24 Complexity
Third approach sa TLE Ara hai gfg pa kya issue hai ??
@@himanshukaushik9223 same
i just got an idea ...its like we know that the array contents will be from 1 to n so if we first sort the given array then the array will be in accending order so ....if we run a loop of 1 to n and if we compare arr[i]==arr[i-1] which are adjcent elements so that means arr[i] is our duplicate so and in the same loop if we find our array sum. then so if we subtract array sum - duplicate then we will remove addition of duplicate element to our array sum ....and then if we subtract sum of n natural numbers or (sum of 1 to n - modified array sum ) then we will got our missing number hence we can return both missing and duplicate .........time complexity -->O(nlogn)+O(n)........space complexity -->O(1)
that's what i did😂😂
Thanks a lot brother
I think the space complexity will be 0(max_element_of_array) if there is mistake please reply.
can i use here floyds tortoise alogorithm to find repeating element
Can anypne plz tell why we started i from 1 from next iteration and also why i
Can we use a different approach run a loop from 0 to n-1(calculate sum) in each iterartion check if number exists in hash if exists store as repeating number if not add to hashmap
after loops is done excecuting we will have repeating number and sum of arr we can calculate sum of n numbers
to get the missing number we can just use formula ( (Es(expected Sum of n numbers) - As(array sum)) + repeating number)
Time complexity: O(N)
Space complexity: O(N)
understood!
Loved it😍
UNDERSTOOD;
To me, XOR approach seemed to be easier to implement...crystal clear explanation 👏
thank you sir
super
my solution for this
public static List Find(int []arr, int n){
Listlist = new ArrayList();
if(arr[arr.length-1] != arr.length){
list.add(n);
}
Arrays.sort(arr);
for (int i = 0; i
I Love this one❤
what if 5 is repeating and 6 is missing both will be in 1 bit segregate then it will be 5^6 in 1 bit part. Please explain
same doubt
understood.
3 approach ma gfg ka link hai usma repeat and missing return karna hai tho dynamically allocation karka karne ha kya reply kar do koi bhi ??
to get 1st set bit can we use (n&~(n-1)) ?
understood bhaiya
now i understand why he was in google his coding skills is too good
how? did he do something different?
what is Gurantee that the val2/val1 always divide with remainder zero?
Loved your solution of xor but we can simply do it with cycle sort if numbers are in range of 1 to n..
you should never alter the input, unless the question specifically says you to do it
Is the 3rd approach getting submitted on GFG? Because mine's isn't.
Xor solution is dope..
UNDERSTOOD
took about 3 hours to finish and understood everything
sum of squares method is failing in GFG at some test case
here's my code
vector findTwoElement(vector arr, int n) {
long long N=n;
long long Sn= (N*(N+1))/2;
long long S2n=(N*(N+1)*((2*N)+1))/6;
long long sum=0;
long long sum2=0;
for(int i=0;i
wth , its now accepted