A constant space solution would be using the XOR operator. If you xor the entire elements present in the array, at the end you’ll be left with the number that appears just once.
@@yousafshoiab1511 if all numbers tripled but some only doubled - you can find that number but not xoring(wich is %2) but summing each bit by modulo 3 so all bits %3 is
result = nums[0] n=len(nums) for i in range(1,n): result^=nums[i] return result or simply use 1 line return reduce(operator.xor,nums) This XOR approach is the most efficient one
@@400elochess but it is isn't it. because the counter is a hashmap which will have the number of different numbers in nums in it. which is O(n) space isn't it?
When dealing with a problem where every element in an array appears twice except for one unique element, a very effective approach is to use the XOR operation. This is because XOR has the property where a ^ a = 0 and a ^ 0 = a. This means that any number XORed with itself results in zero, and any number XORed with zero results in the number itself.
You can use XOR to solve it in constant space and that’s because if we use XOR for the same number the result is 0 and if we use XOR any number with 0 the result es the number 1 XOR 1 = 0, 2 XOR 0 = 2
First of obv XOR. Second, the task description does not fit the function signature. In the description the numbers are given as array, while in the function typing, it's passed as list, what is not the same in Python. And especially for low level operations like XORing, it makes a huge difference in performance and possible speed operations. I'd assume that np.bitwise_xor(nums) should be very close to C/Fortran speed if nums are an array, while for the same thing with a list, the conversion first to a compact memory structure that numpy would do, might be slower than just a for loop xoring it or similar (and probably 2 magnitudes slower than with an array). In case you wonder, a list in CPython is basically a pointer to an array of pointers to arbitrary objects. It's a flexible structure, but very space- and cache inefficient. An array in python is pretty much the same as in C (or detail, it's a struct with an array, plus some slight overhead with counting references to it for garbage collection and typing/array size information, but any operation on it will just similar performant as safe C/Rust/Fortran code, for the latter at least if you use numpy).
i'm at first year of software engineering so i ask people that probably know more than me. My first thought was sorting the array, and every two numbers are going to be equal so if we could cast an "if x[i]≠x[i+1] return x[i]; i++;" Seems like a linear function to me, could take max half of the array length to go through everything. I dont know how hashmaps work in the hardware but i assume counter also just loops through the whole array.
You can just xor all the number in the array and your result is the number wich appear only one time . actually if you xor a number even time your result will be ZERO(for example 3 ^ 3 ^ 3 ^ 3=0) and if you xor a number odd time your result will be your firs number( for example 3 ^ 3 ^ 3 ^ 3 ^ 3=3).
If it is only integers, find min and max, iterate over the range of min to max searching for each occurrence with a minimum appearance of twice, the first one that you find once is the answer. No space of the counter required, albeit maybe not optimal runtime.
Still Not a super optimal one because it is still using an extra space!! You can go with the XOR operator which will eventually cut down the auxiliary space!!
Python3 Use Set. my_set = {} Add each number to the set when first visited, remove it when visited a second time. The remaining member(s) of the set only appeared once. Answer will be: list(my_set). Can anyone think of anything wrong with this solution? Thanks.
A set is linear space. In worst case the set will contain n/2 elements (all the duplicates are in the second half of the areay), and the problem states constant space.
@@cbtheodor "constant extra space" Which means the set is fine, because it will never have more than the space of the list plus a bit for the keys. It isn't my fault python won't let me malloc that space from the start for the set. (But python will malloc plenty pof space, it isn't dumb enough to realloc constantly). And yes, I know the "use XOR" trick. But if a question is this simple I assume there will be a follow-on question to make it harder. The "assume everything but one entry is doubled" is extremely fragile base condition.
Shouldnt the final condition be that If (map.get(i) != 2) Return result as i Since the question only mentions that except one all will be occuring exactly twice. So couldnt a number occur 3 times too based on question & not just once?
I would have just done this using a set... I guess the hasmap approach is faster? def find_single_element(arr): seen = set() for num in arr: if num in seen: seen.remove(num) else: seen.add(num) return seen.pop()
Conveniently ignore "use only constant extra space" Actual solution is x = reduce(operator.xor, nums) Idk if this guy deliberately posts bad solutions/advice to drive engagement. In which case, well done sir, I've played right into your hands.
He has said he trained for data science, so probably never went through basics in machine code or assembly and never saw _Programming Pearls_ or _Hacker's Delight_. And it is good to see different ways to solve the same problem, so I offered a different take too, using python's set. Same thing, different idiom. So cut him a break. I like his channel. Thanks for reading this far!
@@davea136 using a set has the same flaw, O(n) space usage. Btw I've never read those books either. Many people post incorrect things so they get more comments, which makes it more likely their videos will go viral
if you didn't know about Counter() like me... you could solve like this: class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ foundNumber = 0 nums.sort()
hm the size of the hashmap is still n/2+1 if i see that right...depending on how it performs, how about sorting the array and go 2 steps at a time and check of the i==i+1?
XOR to the rescue!!! class Solution { public: int singleNumber(vector& nums) { int result = 0; for(int i = 0; i< nums.size(); i++) { result ^= nums[i]; } return result; } };
If you’re gonna make these solutions seem trivial with these 1 minute shorts, at least come up with the right solution per the problem statement. Hash map is not constant space.
Unfortunately, the video deserves a dislike because the part about constant extra space was completely ignored, and it made the second solution misleading and useless.
Master Data Structures & Algorithms For FREE at AlgoMap.io!
A constant space solution would be using the XOR operator. If you xor the entire elements present in the array, at the end you’ll be left with the number that appears just once.
I think that's not very accurate, if the number of the repeated element was even it works but if odd it won't
Am I right?
@@yousafshoiab1511
that's right in general, but in that problem it says that every element appears twice
This one is nice for sure.
@@yousafshoiab1511 if all numbers tripled but some only doubled - you can find that number but not xoring(wich is %2) but summing each bit by modulo 3 so all bits %3 is
Evryone knows this solution 😂😂😂
result = nums[0]
n=len(nums)
for i in range(1,n):
result^=nums[i]
return result
or simply use 1 line
return reduce(operator.xor,nums)
This XOR approach is the most efficient one
Now THAT is a slick trick.
Xor is a pretty good solution
Does that work in every possibility? Doesn't seem like it, but i didn't test it
@@hodayfa000h it will work in all the cases of integers. If it's a string, we can use stack approach as well.
@@TamilarasuMK the question says an array of integers. It will work on all test cases.
BRO open your eyes 👀 question states constant space :) performance XOR and do it
Constant EXTRA Space
the memory you used to solve, isnt dependant on the input variable.
@@400elochess but it is isn't it. because the counter is a hashmap which will have the number of different numbers in nums in it. which is O(n) space isn't it?
@@jffrysith4365 yeah, for constant space, no for loops
@@jffrysith4365 yes it is, too many don't understand the org aspects
When dealing with a problem where every element in an array appears twice except for one unique element, a very effective approach is to use the XOR operation. This is because XOR has the property where a ^ a = 0 and a ^ 0 = a. This means that any number XORed with itself results in zero, and any number XORed with zero results in the number itself.
You can use XOR to solve it in constant space and that’s because if we use XOR for the same number the result is 0 and if we use XOR any number with 0 the result es the number 1 XOR 1 = 0, 2 XOR 0 = 2
You missed the constant space part in your solution.
Number of elements in the hasmap is constant (0-9)
@@fahimalizain7598 That's not technically constant as it depends on the input.
@@fahimalizain7598 It isn't. It's linear, exactly (n-1)/2
@@fahimalizain7598 it's not 0-9, it's 1-3E4. So in the spirit of the problem it's unbounded.
reduce(lambda acc, n: acc ^ n, nums)
functools.reduce(operator.xor, nums)
More readable I think 😊
First of obv XOR.
Second, the task description does not fit the function signature. In the description the numbers are given as array, while in the function typing, it's passed as list, what is not the same in Python. And especially for low level operations like XORing, it makes a huge difference in performance and possible speed operations.
I'd assume that np.bitwise_xor(nums) should be very close to C/Fortran speed if nums are an array, while for the same thing with a list, the conversion first to a compact memory structure that numpy would do, might be slower than just a for loop xoring it or similar (and probably 2 magnitudes slower than with an array).
In case you wonder, a list in CPython is basically a pointer to an array of pointers to arbitrary objects. It's a flexible structure, but very space- and cache inefficient. An array in python is pretty much the same as in C (or detail, it's a struct with an array, plus some slight overhead with counting references to it for garbage collection and typing/array size information, but any operation on it will just similar performant as safe C/Rust/Fortran code, for the latter at least if you use numpy).
i'm at first year of software engineering so i ask people that probably know more than me.
My first thought was sorting the array, and every two numbers are going to be equal so if we could cast an "if x[i]≠x[i+1] return x[i]; i++;"
Seems like a linear function to me, could take max half of the array length to go through everything.
I dont know how hashmaps work in the hardware but i assume counter also just loops through the whole array.
ok nvm i took for granted the sorting algorithm, i take it back
Greg Hogg, This is amazing! I can't stop smiling!
Hahah why's that
Posting suboptimal solution to increase engagement 😂
val list = listOf(1, 5, 4, 3, 1, 4, 5, 2, 3)
val result = list.reduce { a, b -> a.xor(b) }
Why not take XOR of all elements ?
Fast and Space Optimized
You can just xor all the number in the array and your result is the number wich appear only one time .
actually if you xor a number even time your result will be ZERO(for example 3 ^ 3 ^ 3 ^ 3=0) and if you xor a number odd time your result will be your firs number( for example 3 ^ 3 ^ 3 ^ 3 ^ 3=3).
If it is only integers, find min and max, iterate over the range of min to max searching for each occurrence with a minimum appearance of twice, the first one that you find once is the answer. No space of the counter required, albeit maybe not optimal runtime.
[1,1, 99999, 100000, 100000]
Your program will iterate from 1 99,999 before finding the solution.
This uses linear extra space
You make it look so easy
It's a planned, recorded video. This doesn't show the hours I've put in to learning this :)
CAN ALSO SOLVE VIA HASHING HAVING ARRAY OF N+1 SIZE AND PUTTING FREQUENCY TO THE INDEX.
thats not constant space as the longer the array the bigger the hashmap you need
@@amanthinks374 who said i was talking about constant space. that's a way i offered
Found = set()
For x in nums:
If x in found: found.remove(x)
Else: found.add(x)
Return found
make a freq array - store each num in their index.
for each element in nums, return i if arr[i] ==1
You need to find max first, also very space-consuming, use set or dict
@@phusicus_404 max is in the constraints, you make the size the same as that. so it’s O(n) time and O(1) space.
It can be easily done as a one liner using list comprehension
Still Not a super optimal one because it is still using an extra space!!
You can go with the XOR operator which will eventually cut down the auxiliary space!!
Is every single "Veteran Dev" solution to throw said thing into a hash map?
It's pretty common yes hahaha
Ontario has the best developers, gems in the small towns that all end up in Toronto or Montreal.
Python3 Use Set.
my_set = {}
Add each number to the set when first visited, remove it when visited a second time. The remaining member(s) of the set only appeared once.
Answer will be:
list(my_set).
Can anyone think of anything wrong with this solution? Thanks.
Just return number if it's is present in set
If single numbers would be multiple then yes
A set is linear space. In worst case the set will contain n/2 elements (all the duplicates are in the second half of the areay), and the problem states constant space.
@@cbtheodor "constant extra space"
Which means the set is fine, because it will never have more than the space of the list plus a bit for the keys. It isn't my fault python won't let me malloc that space from the start for the set. (But python will malloc plenty pof space, it isn't dumb enough to realloc constantly).
And yes, I know the "use XOR" trick. But if a question is this simple I assume there will be a follow-on question to make it harder. The "assume everything but one entry is doubled" is extremely fragile base condition.
Just use XOR.
Simplest is using xor
Using the xor will the optimal one your code is just an better method
Shouldnt the final condition be that
If (map.get(i) != 2)
Return result as i
Since the question only mentions that except one all will be occuring exactly twice. So couldnt a number occur 3 times too based on question & not just once?
Scala one-liner:
def singleNumber(nums: Array[Int]): Int = nums.foldLeft(0)(_ ^ _)
Use xor
I would have just done this using a set... I guess the hasmap approach is faster?
def find_single_element(arr):
seen = set()
for num in arr:
if num in seen:
seen.remove(num)
else:
seen.add(num)
return seen.pop()
Int ans=0;
For i-0 to nums.size-1
ans=nums(I)^ans;
Return ans;
Why not just use a stack?
I know till the hashmap part, but keep forgetting the Counter function and making a loop instead
It's not just function, more like a constructor
What if we use .count() ?
Constant extra space... but uses a hash map of n elements...
Conveniently ignore "use only constant extra space"
Actual solution is x = reduce(operator.xor, nums)
Idk if this guy deliberately posts bad solutions/advice to drive engagement. In which case, well done sir, I've played right into your hands.
He has said he trained for data science, so probably never went through basics in machine code or assembly and never saw _Programming Pearls_ or _Hacker's Delight_. And it is good to see different ways to solve the same problem, so I offered a different take too, using python's set. Same thing, different idiom. So cut him a break. I like his channel. Thanks for reading this far!
@@davea136 using a set has the same flaw, O(n) space usage. Btw I've never read those books either. Many people post incorrect things so they get more comments, which makes it more likely their videos will go viral
if you didn't know about Counter() like me... you could solve like this:
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
foundNumber = 0
nums.sort()
for i in range(len(nums)):
if len(nums)
what is the site he's using to test his solution?
Leetcode
return min(Counter(nums).items(),key = lambda x : x[1])[0]
hm the size of the hashmap is still n/2+1 if i see that right...depending on how it performs, how about sorting the array and go 2 steps at a time and check of the i==i+1?
Sorting itself is O(n log n)
What about xor?
nobody uses it in real world
Cold in Canada eh?
Is bit operation not available in python?
I think bitwise XOR is more optimal
Would a set() approach work here as well?
Yep, add to a set if it's not in it, remove from a set if it is. The resulting set will be a singleton containing the solution.
@@alxjones Wonderful! Thank you so much for responding!
Meanwhile XOR operator: 🗿🚀
Binary search left the chat
You have not read the follow up 😊
Lol
XOR to the rescue!!!
class Solution {
public:
int singleNumber(vector& nums) {
int result = 0;
for(int i = 0; i< nums.size(); i++)
{
result ^= nums[i];
}
return result;
}
};
I really like your videos.
Thank you, that means a lot :)
Better use an hashset
If you’re gonna make these solutions seem trivial with these 1 minute shorts, at least come up with the right solution per the problem statement. Hash map is not constant space.
My FOMO made me think Toronto is a new framework 🤦♂️
Nice solution
Xor
Learnt this from hackerrank💀
Xor bro xor
Yes!
xor
You usually get it right but not this time.
So basically the solution to everything is a hash map 😂
Xor would be better 😅
analog electronisc say that even idiot can count to 1, so set is enough.
One line solution (but not optimized thought) for a given list called l:
{l.count(i): i for i in l}[1]
Hashmap is linear in space lol
When wannabe developers make videos on TH-cam. this is a constant space question using XOR operator.
When wannabe idiots write comments
Let me give you a much better solution
Just do the xor operation of all element and you will get your answer ❤😂
Unfortunately, the video deserves a dislike because the part about constant extra space was completely ignored, and it made the second solution misleading and useless.
Bit xor of
Huh? Just XOR! What’s wrong with this channel? People watching this and learning bad coding. 💀💀
If you disagree with this channel then you're a bad programmer
@@paulblart7378 huh? you want to compete with me? Bruh, I can walk the talk. If you patronize this channel, you're a bad and garbage programmer.
Failed! O(n) space!!
let tab=[1,1,2,3,3,4,4]
let value=0
tab.forEach(val=>{
tab.filter(val1=>val1===val).length == 1 ? value = val : null
})
console.log(value) // 2
Constant space wtf
const singleNumber = list => {
let checked = new Set(),
singles = new Set();
list.forEach(value =>
checked.has(value)
? singles.delete(value)
: (checked.add(value), singles.add(value)));
return singles.size === 1 ? [...singles].at(0) : 'not single number';
}
Use xor
Xor