Don't leave your software engineering career path to chance. Make sure you're interview-ready with Exponent's software developer interview prep course: bit.ly/3wFcUtn
My solution: create a Hash Set, for each number in list, add them to the hash, if it's already in it, return it (duplicated) O(n) (1 loop) set_nums = set() for n in range(len(nums)): if nums[n] in set_nums: return nums[n] set_nums.add(nums[n]) return -1
It was asked not to modify the array but this answer modifies it. We need to use Floyd's cycle finding algorithm to meet the requirements of using constant space and O(n) time.
It wouldn’t be hard for him to fix it. Since he max some numbers negative, just loop thru them to make them positive once again. Then return the duplicate.
for those who are l;ooking for the correct solution: int findDuplicateCal(int* arr, int size) { int n = size - 1; // Calculating the expected sum of the first n natural numbers using the formula: n(n+1)/2 int expected_sum = n * (n + 1) / 2; // Calculating the actual sum of the array elements int actual_sum = 0; for (int i = 0; i < size; i++) { actual_sum += arr[i]; } // The duplicate number is the difference between the actual and the expected sum return actual_sum - expected_sum; }
The previous one I watched (product array except own number) they forgot to mention that the question states no division. That completely changes the question, I thought there's a way faster solution using division and she will probably explain it at the end, not taking the current solution serious (since I had an O(N) solution in mind using the division). Please add the full question then in an overlay so people who watch can properly code along. @Exponent. Thanks for making the content available.
Sure but in a real interview the interviewer will just point that out and even if he can't figure out the answer (tortoise and hare cycle detection), he'll be praised by the interviewer for being able to come up with this answer
@@S__ArslaanIt works. And, In the problem statement it's given that the array contains n+1 elements ranging from 1 to n. Therefore the example array you provided doesn't match the problem statement.
Duplicate Value = Sum(array) - (N * (N+1))/2. For example, Array = [5, 2, 4, 3, 1, 4], and N=5. Sum(Array) = 19, (5*(5+1))/2 = 15. Difference is the duplicate value = 19 - 15 = 4. Just iterate over array if Index is needed for duplicate value.
@@chowcao1753if you check all constraints again then you will realise that [3,3,3,3,3] is also a valid input case. Here also all elements are ranging from 1 to 4 if size is 5. And she is not saying element is repeated only once.
I don't get why all these mock Interviews are skipping over the simplest/obvious solutions. It's like the candidates don't even take a minute to think about the problem and just jump straight into solutions.
@@iampavel865 I don't exactly know what you mean, but the key to this problem is, that the array consists of the first n natural numbers plus one duplicate. For the sum of the first n natural numbers you can use the Gaussian Sum Formula. Henceforth, since the array consists of exactly this sum and one duplicate number, we can retrieve the duplicate by subtracting the sum of the Gaussian Sum Formula.
No problem. If you're wondering why my function uses len * (len - 1) / 2 for the Gaussian Sum Formula, that is because the Gaussian Sum Formula is for the first n natural numbers and the array in this problem has a size of n+1 numbers. So my variable "len" is actually equal to n+1, that's why I needed to replace each n in the formula with (n-1). So the Formula is n * (n+1) / 2 and then becomes (n-1) * ((n-1)+1) / 2 = (n-1) * n / 2 Or just len * (len-1) / 2 with my variable.
Hey gabriellemarie13! To ace your technical interviews (as an entry-level SWE), you need to go beyond coding and syntax. You should read up about data structures and algorithms (how to apply them and how to implement them). You should learn about space and time complexity and how to optimize your functions to improve its performance. If you want a one-stop platform to learn and prep for your SWE role, you can check out our SWE interview course here: www.tryexponent.com/courses/software-engineering Hope this helps!
For me the solution is Sum(array) - ( sum((index +1) for n indexes) - array.length) Ultimately the idea is the sum of an array element (which has n+1 elements ) - ( sum of 1 to n elements)
Summing all the elements won't work in the case you have an element duplicated more than once ,, the same for xor(xor(arr),xor(1-n)) would work only for even nuber of duplications , so i think he gave the best general solution, great job
def find_rep(lst): for i in range(len(lst)): rep = 0 if i>0: rep= lst[i-1] if lst[i] == rep: return rep return "Nothing's repeating" lst = list(map(int,input().split())) print(find_rep(lst)) # This will do?
You are using extra space so it failed. The correct solution is: public static int findDup(int arr[]) { for(int i = 0; i < arr.length-1; i++) { if(arr[i] == arr[i+1]) return arr[i]; } return -1; }
For modifying the array, it could be simply returned back with an extra loop and we would still have it O(2N) = O(N), so I think he has the best solution.
Since the array was constructed with n+1 order. then following script will suffice: int findDup(int arr[]) { for(int i = 0; i < arr.length-1; i++) { if(arr[i] == arr[i+1]) return arr[i]; } return -1; }
They should have asked this to a math not CS student. Just sum the array and subtract the triangle formula n*(n+1)/2 to get the answer. Google rejected me twice; too bad I didn't get this problem.
@@sky_beast5129 The input ils perfectly valid, "repeated" doesn't mean it appears only twice. The interviewee in the video took care of checking his solution covers this case.
Here's a JS solution, using memoization, O(n) time complexity and not modifying the original array: function findDuplicate(arr) { const memo = {} for (let i = 0; i < arr.length; ++i) { if (arr[i] in memo) { memo[arr[i]] = memo[arr[i]] + 1 } else { memo[arr[i]] = 1 } } return Object.keys(memo).filter((k) => memo[k] !== 1) } // time complexity: O(n)
Marking a[i]-1 value as negative at each index and while doing this, if you already find a negative value, you can simply return i, because that's your duplicate value.
Hey teluguanimetoon2811, thanks for solving it along with us! Unfortunately, your solution finds the missing element and not the repeated element so it won't work for this case. I think you might be able to tweak the logic in your code to solve this problem though. You've got this! 💪
@@MahmoudAhmed-sc7jg yeah actually I need to do few more steps. After doing xor of all numbers and 1 to n, whatever the result xor will be there, i need to get the right most set bit of that xor result. Then I will xor all numbers which are having that bit set in one variable and the numbers which are not having that bit set in another variable. Now one of the variable contains the duplicate number, we can easily check that with a for loop.
Cool trick with the 2nd solution - deriving a hash from index. However, The time complexity of his 1st solution is not O(n2) but better as his inner loop has j=i+1 so the time complexity is the combinations formula i.e (n*(n-1)/2)
perhaps i worded it badly (and fixed it now).. i wanted to say that the diff between the quads is big.. and that the combinations one takes far less time.. i.e O(n^2) is approx double that of O(n*n-1/2)..
This is an incorrect answer lol should mention this solution is wrong and why in the video. This is kind of the opposite of providing good interview prep material. I would've rejected this candidate.
Don't leave your software engineering career path to chance. Make sure you're interview-ready with Exponent's software developer interview prep course: bit.ly/3wFcUtn
Frequency count or cyclic sort or hashmap etc
My solution:
create a Hash Set, for each number in list, add them to the hash, if it's already in it, return it (duplicated)
O(n) (1 loop)
set_nums = set()
for n in range(len(nums)):
if nums[n] in set_nums:
return nums[n]
set_nums.add(nums[n])
return -1
That exercise is mind blowing for me, even with him providing a resolution proposal
It was asked not to modify the array but this answer modifies it. We need to use Floyd's cycle finding algorithm to meet the requirements of using constant space and O(n) time.
Exactly! so he actually failed.
Wouldnt using XOR better??
@@nameless2850 Will it be considered as an extra space?(To store the XOR's in a variable)
It wouldn’t be hard for him to fix it. Since he max some numbers negative, just loop thru them to make them positive once again. Then return the duplicate.
for those who are l;ooking for the correct solution:
int findDuplicateCal(int* arr, int size) {
int n = size - 1;
// Calculating the expected sum of the first n natural numbers using the formula: n(n+1)/2
int expected_sum = n * (n + 1) / 2;
// Calculating the actual sum of the array elements
int actual_sum = 0;
for (int i = 0; i < size; i++) {
actual_sum += arr[i];
}
// The duplicate number is the difference between the actual and the expected sum
return actual_sum - expected_sum;
}
Best comment ever, start with any solution, and dont try to give the best solution at first. Better to have something then nothing
Question asked not to modify the array
I was thinking the same.
We can again able to restore back the original elements .
for(int i=0;i
@@HariKrishnan-ff4hf without modifying the array means you can’t change its values in the first place. You should assume it’s a read-only array
The previous one I watched (product array except own number) they forgot to mention that the question states no division. That completely changes the question, I thought there's a way faster solution using division and she will probably explain it at the end, not taking the current solution serious (since I had an O(N) solution in mind using the division). Please add the full question then in an overlay so people who watch can properly code along. @Exponent. Thanks for making the content available.
Sure but in a real interview the interviewer will just point that out and even if he can't figure out the answer (tortoise and hare cycle detection), he'll be praised by the interviewer for being able to come up with this answer
Take sum and subtract from sum(1 to n) to get the duplicate value.
My first thought lol!
sum(all) - n*(n+1)/2
No it won't work... If arr=1, 2,2,4 sum Of array=9, sum(1-4) =10... Subtract and you get 1 but the duplicate value is 2
@@S__ArslaanIt works. And, In the problem statement it's given that the array contains n+1 elements ranging from 1 to n. Therefore the example array you provided doesn't match the problem statement.
@@S__Arslaanthe array would be 1,2,2,3
Duplicate Value = Sum(array) - (N * (N+1))/2. For example, Array = [5, 2, 4, 3, 1, 4], and N=5. Sum(Array) = 19, (5*(5+1))/2 = 15. Difference is the duplicate value = 19 - 15 = 4. Just iterate over array if Index is needed for duplicate value.
🤯🤯
how does it work for [2,2,2,2,2]
@@wasifnehvi7705 the diff should be within 1 and n, for your case is 4. But it turns out that the diff is 0, therefore, the input is invalid!
read the question first@@wasifnehvi7705
@@chowcao1753if you check all constraints again then you will realise that [3,3,3,3,3] is also a valid input case.
Here also all elements are ranging from 1 to 4 if size is 5.
And she is not saying element is repeated only once.
let tab=[1,2,3,5,4,1,6,7,8]
let repeated;
tab.forEach(val=>tab.filter(vall=>vall===val).length > 1 ? repeated=val :null )
console.log(repeated) // 1 & foreach loop doesn't change the original array
Iterate once finding the array sum, then subtract the sum of n numbers : Ans = ArrSum - (n*(n+1)/2)
I don't get why all these mock Interviews are skipping over the simplest/obvious solutions. It's like the candidates don't even take a minute to think about the problem and just jump straight into solutions.
The number can be repeated more than twice too. That's why it won't work.
@@sharatchandra1586 Hmmmm. Feel like someone should clarify that. Am I the only one would infer 2 times by the word duplicate?
@@sharatchandra1586, as per my understanding, duplicate means 2 unless stated otherwise.
@@sharatchandra1586 also, there are only n+1 numbers in the array, that stresses more on just one number repeated twice.
size_t FindDuplicateNumber(size_t* arr, size_t len)
{
size_t sum = 0;
for(size_t i = 0; i < len; i++)
sum += arr[i];
return sum - len * (len - 1) / 2;
}
what is this algorithm called?
@@iampavel865 I don't exactly know what you mean, but the key to this problem is, that the array consists of the first n natural numbers plus one duplicate. For the sum of the first n natural numbers you can use the Gaussian Sum Formula. Henceforth, since the array consists of exactly this sum and one duplicate number, we can retrieve the duplicate by subtracting the sum of the Gaussian Sum Formula.
@@sky_beast5129 Thank you, i did not know about this formula.
No problem. If you're wondering why my function uses len * (len - 1) / 2 for the Gaussian Sum Formula, that is because the Gaussian Sum Formula is for the first n natural numbers and the array in this problem has a size of n+1 numbers. So my variable "len" is actually equal to n+1, that's why I needed to replace each n in the formula with (n-1).
So the Formula is n * (n+1) / 2
and then becomes
(n-1) * ((n-1)+1) / 2 = (n-1) * n / 2
Or just len * (len-1) / 2 with my variable.
Why not just use a hashmap and store the count of each item in the array and then return the number with count 2 in the hashmap.
you were not supposed to modify the array right
I am fairly new to coding, how can I start preparing for technical interviews and land a job as a software engineer?
Hey gabriellemarie13! To ace your technical interviews (as an entry-level SWE), you need to go beyond coding and syntax. You should read up about data structures and algorithms (how to apply them and how to implement them). You should learn about space and time complexity and how to optimize your functions to improve its performance.
If you want a one-stop platform to learn and prep for your SWE role, you can check out our SWE interview course here: www.tryexponent.com/courses/software-engineering
Hope this helps!
@@tryexponent thank you so much! I will do my research on that :)
She said, without modifying the array but the solution provided modifies the array.
what if there is a greater element than length of array? then it will throw arrayindexoutofbound exception
yes
Pretty easy question
he is modifying the array which we can't do , right?
Yep.
as per the constraint yes. he modified and thus did not meet the requirements.
For me the solution is
Sum(array) - ( sum((index +1) for n indexes) - array.length)
Ultimately the idea is the sum of an array element (which has n+1 elements ) - ( sum of 1 to n elements)
How would we solve if the input is [1, 100, 0, -1, 100, 50, 60]?
Summing all the elements won't work in the case you have an element duplicated more than once ,, the same for xor(xor(arr),xor(1-n)) would work only for even nuber of duplications , so i think he gave the best general solution, great job
Excellent explanation, thanks
question says only one extra duplicate and not more than once . n+1 terms and numbers ranging from 1 to n with one duplicate . 0:05
First of all he was not supposed to modify the array, if we can then we can do simple cyclic sort, its done
@@darkhunter882we can simply run extra for loop and make all values positive. And we got our input back as it is.
def find_rep(lst):
for i in range(len(lst)):
rep = 0
if i>0:
rep= lst[i-1]
if lst[i] == rep:
return rep
return "Nothing's repeating"
lst = list(map(int,input().split()))
print(find_rep(lst))
# This will do?
You are using extra space so it failed. The correct solution is:
public static int findDup(int arr[]) {
for(int i = 0; i < arr.length-1; i++)
{
if(arr[i] == arr[i+1])
return arr[i];
}
return -1;
}
@@MoMoGammerOfficial could you explain what's wrong
int main() {
int n = 10;
int arrSum = 0;
int arr[n+1] = {1,2,3,4,5,5,6,7,8,9,10};
for(int i = 0; i
For modifying the array, it could be simply returned back with an extra loop and we would still have it O(2N) = O(N), so I think he has the best solution.
I have run this code, it's fails on test cases like [2,2,4,3,1].
subtract sum of 1 to n from sum of all elements present in array, simple 🙂
Can we do sum(1 to n+1) elements - (n*(n+1)/2)=Ans
No it will fail for cases which have same number duplicated more than one time
@@sidvyas Exactly.
Since the array was constructed with n+1 order. then following script will suffice:
int findDup(int arr[]) {
for(int i = 0; i < arr.length-1; i++)
{
if(arr[i] == arr[i+1])
return arr[i];
}
return -1;
}
But this would only work if the array is sorted.. it's not given in the question..
Chapters (Powered by ChapterMe) -
00:00 - Introduction
00:40 - Question
01:19 - Answer
07:39 - Test cases
09:30 - Tips
Would it using a bitarray with the int go against the rule of using constant space? He is using now set, that's not constant space
Using a dictionary(hashmap), adding any non existing number to it and returning the number if it exist in it with one for loop, would be O(n) too.
She asked him to keep the space complexity O(1)
yeah, but need Time Complexity to be O(N). This would be easy and just like two sum in leetcode which would use hash map
They should have asked this to a math not CS student. Just sum the array and subtract the triangle formula n*(n+1)/2 to get the answer. Google rejected me twice; too bad I didn't get this problem.
Yeah too bad, you would have been rejected again. Doesn’t work for [1,1,1,2]
@@aup720 It does not work for the input [1,1,1,2] because the input is invalid. The question states, that only one number is repeated in the array.
@@sky_beast5129 The input ils perfectly valid, "repeated" doesn't mean it appears only twice. The interviewee in the video took care of checking his solution covers this case.
@@sky_beast5129input is perfectly valid
This solution will work for {1,44,2,44}? I think no
Nums are only in range 1 - n. So if length of arr is 4, you can only have nums from 1-3 and one duplicated number
@@itsdadannyboy ohh i see i was looking for extended solution and didnt took close look on array constraints 😅😅
Here's a JS solution, using memoization, O(n) time complexity and not modifying the original array:
function findDuplicate(arr) {
const memo = {}
for (let i = 0; i < arr.length; ++i) {
if (arr[i] in memo) {
memo[arr[i]] = memo[arr[i]] + 1
} else {
memo[arr[i]] = 1
}
}
return Object.keys(memo).filter((k) => memo[k] !== 1)
}
// time complexity: O(n)
i also came up with this solution..But that's not constant extra space.. it's O(n) extra space..
Marking a[i]-1 value as negative at each index and while doing this, if you already find a negative value, you can simply return i, because that's your duplicate value.
is this correct
#include
int missing_element(const int *a,int &size){
int total_array=0;
int sum_of_n=0;
for(int i=0;i
Hey teluguanimetoon2811, thanks for solving it along with us!
Unfortunately, your solution finds the missing element and not the repeated element so it won't work for this case.
I think you might be able to tweak the logic in your code to solve this problem though. You've got this! 💪
Sort array and loop array compare ith and i-1 element if both are same, break loop return value
sorting the array is modifying it
@@MrHenryG123 Exactly!
@@MrHenryG123 not if it's passed in by value, she never mentioned it had to be passed in by L value reference.
XOR(XOR(array), XOR(1 to n))
This approach will help you to find the missing number in the array (1 to n) not to get the duplicated one
@@MahmoudAhmed-sc7jg yeah actually I need to do few more steps. After doing xor of all numbers and 1 to n, whatever the result xor will be there, i need to get the right most set bit of that xor result. Then I will xor all numbers which are having that bit set in one variable and the numbers which are not having that bit set in another variable. Now one of the variable contains the duplicate number, we can easily check that with a for loop.
Did he modify the array?
Yes he did, it was not what was asked at all
leetcode 268 just xor all elements and 1 to n
Cool trick with the 2nd solution - deriving a hash from index. However, The time complexity of his 1st solution is not O(n2) but better as his inner loop has j=i+1 so the time complexity is the combinations formula i.e (n*(n-1)/2)
Correct me if iam wrong but approx that's O n^2 only.
perhaps i worded it badly (and fixed it now).. i wanted to say that the diff between the quads is big.. and that the combinations one takes far less time.. i.e O(n^2) is approx double that of O(n*n-1/2)..
good job friend!!
We can count the numbers in a loop (=n), and then check if there is a number greater than one in the new array.
Am I wrong?
this would work but will not be a constant space solution.
It works only for positive integers
Which is fine, since the problem specifies numbers in range 1 to N
Use xor
Bro all these comments just use Copilot
just sum them all?
what is the point of summing them?
you can find sum of all numbers 1 to n in constant time then you can subtract that from the sum of the array to find the number that is repeated
@@alanwang8733 have you tried this approach with some inputs?
(1,2,2)
sum of 1 and 2 is 3 sum of array is 5 duplicate number is 2 no?
This is an incorrect answer lol should mention this solution is wrong and why in the video. This is kind of the opposite of providing good interview prep material. I would've rejected this candidate.
(1) sum of first n numbers : n*(n+1)/2
(2) sum of elements in array : sum of first n numbers + duplicate number
ans = (2) - (1)
time = O n
space = O 1
The requirement says you cant use extra space, and you cant modify the array input as well so summing to find dup is not a solution.