A bit confused with it. The numbers in that array can be of large size. Doesn't that increase the complexity? As every bit position is counted each time.
@@muhammadmohaiminulislam7189 In Time complexity, we use N to express the size of the array. Bitwise operations are considered O(1), just like addition and subtraction. When we add up N numbers, we say it is O(n), right? We don't consider how long each number is. The reason is because addition/subtraction/mult/division/bitwise operations are considered "primitive" operations, they always take the same amount of time in modern cpu architecture.
We can think of it as the following facts:- 1. XOR of a number with itself is 0 2. XOR of a number with 0 is the number itself 3. XOR is commutative so the order of numbers does not matter
Hey Errichto! Really appreciate these videos man, I'm just starting my competitive programming journey because i was invited to join my university's team, and I'm glad that your videos exist out here cause the best way I learn is through consumption of youtube videos in my free time. Thanks a lot, and keep up the good work!
Great videos, your actual skill is insane and I love the way you wrap up the problem at the end of the video with some further information and explanaition! Keep it up, Errichto
That's a very good explanation. Hopefully, my video is still useful because I explain why we would think about bits (or parity) in the first place. So if you don't think about XOR, what logic could get you there.
I just want to tell you that these videos helped me immensely. a huge thing thank you. it would be amazing if you did more similar series. I’m learning so much
Thanks man for your such efforts I am a beginner and I have tried starting competitive programming even once before but I gave up due to lack of knowledge and frustration of not improving and remaining stuck....hope to get past this time with your guidance and motivation.
I request to activate ads , your so so so good at teaching , and having thousands of subs , I would happily watch 2 ads at the start and 2 at the end to watch such content
For those who have difficulty understanding this like I had, imagine the integers as a stack in tetris, where same number disappear because of ex-or operation, leaving only the number appearing once.
Once you solved it, you can click the 'Solution' button and see the editorial with 4 different approaches and complexities: (1) List operation, (2) Hash Table, (3) Math and (4) Bit Manipulation. The last one is the only one with Space Complexity of O(1).
i add an extra: - XOR a number with itself *odd number of times* the result is number itself. - XOR a number *even number of times* with itself, the result is 0. and because of the associativity and commutativity of XOR operation, Xoring the list of numbers will give you the unique number
did you ever felt depressed when you had to see editorials of problems continuously during your beginner's days? Also what did you do for math and numbers theory problems?
XOR a number with itself is 0, so the numbers that appear twice in the list will XOR themselves out leaving behind the desired number, the only number without a duplicate. The same principle applies when you think of it in terms of bit parities. For each bit of each number in the list, the duplicate bit between two numbers in the list will XOR themselves out to 0, leaving behind the desired bit. If the leftover desired bit is 0, then 0 XOR 0 is 0, if the leftover is 1, then 0 XOR 1 is 1.
Great video. Could you also show the "Submission Detail" (runtime and memory usage) of your solution the next time so I could compare how bad my solution was to yours haha
I think the statement of this problem is a bit vague. Because for the test case [2,1,2,1,4,4,4,4], the expected answer is 0, while from the problem statement, I think it should be 4.
Excellent solution. Thanks for sharing. Do you mind if I asked what would happen if it was string array and they wanted you to find duplicate string? How would you approach to problem ? I do not know answer but I like way you aprroach to problems. That is why I asked.
first find the xor of whole array=n...now partition the array with number having kth bit as 1 and 0.....since now the unique numbers have been seperated..we can apply the same technique individually
if in an array exactly1 number is duplicate then how to find it in time complexity of O(n) and space complexity of O(1). Also suggest something other than hash map technique.
Pratyush Kumar you calculate the same XOR sum, then you can use a bitwise AND operator on that value and the same value after applying the logical not operator minus 1. It would look like xorSum &= ~(xorSum - 1) then return xorSum. Edit: here’s the geeks for geeks link where you found this problem www.google.com/amp/s/www.geeksforgeeks.org/find-two-non-repeating-elements-in-an-array-of-repeating-elements/amp/
My confusion is XOR or 2 numbers give another number. For example, if the list of numbers is [4,2,1,2,1], then 4 ^ 3 will result in 7. Am I missing something?
@@psychorameses sorry I meant to write 4^2. Yet again, isn't 4^2 = 6? because in bits 100 ^010 = 110 which is 6. I am little confused why bitwise XOR would return 4 in case of 4^2. I would appreciate clarification
lets say xor is like addition a+b+c = c+a+b = b+a+c (that is order wont matter) in our list we do 4^2^1^2^1 which can be also written as 4^(2^2)^(1^1) also a number XORed with itself is zero => 4^(0)^(0) also any number XORed with 0 is the number itself => 4 ---> our answer
Does it still work if the list is not sorted? I thought the list wasn't necessary sorted so I didn't think about this approach. For example, if the array of integers is [10, 12, 10] then at some point the operation would be : 10 ^= 12.
The statement isn't precise. It should say that the special number occurs exactly once. You can kind of guess it from words "single once" or the title "single number". I didn't even think about it because I just thought: yeah, I know this problem, whatever.
@@alexandercasian4904 No, I'm just saying that the sample in the comment above could be considered valid (all elements except for one occur twice, nothing is stated about the number of occurrences of the exception).
The total even numbers in the array was 3. So it is obvious that the answer is an even number. And so the least significant bit is 0. But then he considered the second least significant bit. I didn't understand the approach from here. Can anyone please explain it to me?
i just joined codeforces and i was doing this problem of wrong substraction program.c:3:1: error: unknown type name 'import' it shows this error java code
import java.util.Scanner; public class P { public static void main(String[] args) {
Scanner sc = new Scanner(System.in); int n = sc.nextInt() ; int k= sc.nextInt() ;
Why is this getting compile error ? class Solution { public: int singleNumber(vector& nums) { int n = nums.size(); for(int i = 0; i < n; i++){ int val = nums[i]; int freq = count(nums.begin(),nums.end(),val); if(freq > 1){ continue; } return val; } }
I had no idea myself just learned the basics in the past fifteen minutes. I am sharing what I have learned from my observation but I could be wrong. Convert 4 and 5 to their binary representation which would be 100 and 101 respectively. Now apply xor operation to corresponding bits. 1 xor 1 becomes 0, 0 xor 0 becomes 0 and 0 xor 1 becomes 1. What we finally get is 001 which in base 10 is 1. Therefore 4 xor 5 (also represented as 4^5) should be 1. Point to note is that for any two numbers in their binary representation like bits become 0 and unlike bits become 1. This means x^x will become 0 and x^0 becomes x. Since order doesn't matter in xor, in the above video when numbers are xored in succession, every time a number xors the result it will cancel out its effect if it ever was a part in previous xor steps. So if you encounter a number twice in an array and you were xorring every element it would be like as if you never encountered a particular number if it presents itself twice in the array. So if all numbers are repeated only once and a particular number is never repeated we will have that number as the final result. Hope I was not blatantly wrong with my description but this is what I have gathered from what I read till now.
@@arunp9437 2^2=4-->4^2=16-->1^2+6^2=37-->3^2+7^2=58-->5^2+8^2=89-->8^2+9^2=145-->1^2+4^2+5^2=42-->4^2+2^2=20-->2^2+0^2=4(here we get into the loop,because already after 2 we have got 4), so it never evaluates to 1.Hence, not a happy number.
Now I came up with a nice way to put it:
For every bit, bitwise XOR holds total parity of this bit in numbers that you xored.
A bit confused with it. The numbers in that array can be of large size. Doesn't that increase the complexity? As every bit position is counted each time.
@@muhammadmohaiminulislam7189 In Time complexity, we use N to express the size of the array.
Bitwise operations are considered O(1), just like addition and subtraction. When we add up N numbers, we say it is O(n), right? We don't consider how long each number is. The reason is because addition/subtraction/mult/division/bitwise operations are considered "primitive" operations, they always take the same amount of time in modern cpu architecture.
@@MattYang
Oh i didn't notice the solution has only 1 loop. My confusion wasn't about complexity of xor ing though. Thanks anyways.
@Errichto Why even numbers count is 3? Isn't also 2? Maybe we are asumming beforehand that S is 2...?
@@JJ-ox2mp
Maybe he was talking about the later example. Where there are 5 numbers, of those 3 are even(4,2,2) and 2 are odd(1,1)
I hope Errichto earns enough money from RUclips so that he can be our full time teacher. 😂
@Rajath R Pai genaddy: hold my keyboard!!
Errichto Indeed Errichto is the best
We can think of it as the following facts:-
1. XOR of a number with itself is 0
2. XOR of a number with 0 is the number itself
3. XOR is commutative so the order of numbers does not matter
I am new to cp
From your comment I understood it
Thanks 😊
@@aanchalsharma5264 mai bhi... all the best 👍💯
Will this work in python? Can you suggest what logic to I apply, except using count method
@@ankitkumar6130 i think python also has this bitwise XOR operator, you can try that.
@@lovvyparhar393 can you suggest some different logic
Hey Errichto! Really appreciate these videos man, I'm just starting my competitive programming journey because i was invited to join my university's team, and I'm glad that your videos exist out here cause the best way I learn is through consumption of youtube videos in my free time. Thanks a lot, and keep up the good work!
Great videos, your actual skill is insane and I love the way you wrap up the problem at the end of the video with some further information and explanaition! Keep it up, Errichto
The idea is based on following two facts.
a) XOR of a number with itself is 0.
b) XOR of a number with 0 is number itself.
Thank you, that explained it for me.
Thanks
That's a very good explanation. Hopefully, my video is still useful because I explain why we would think about bits (or parity) in the first place. So if you don't think about XOR, what logic could get you there.
You need the fact that it's commutative, otherwise it doesn't work.
Imagine you were multiplying matrices, the order matters in that case.
@@Errichto yes, that was the whole idea behind the video, thanks errichto.
Am I the only noob coder in this channel? I barely know little bit of C language but I like the way he explains the solution. loving your content man.
Very well explained! Most explanations just say 'XOR it'. But you explained very cleanly WHY we might need to do that. Thank you!
I just want to tell you that these videos helped me immensely. a huge thing thank you. it would be amazing if you did more similar series. I’m learning so much
Saw your reminder yesterday and solved it.thanks otherwise i would have forgotten to do it.
Thanks for uploading this. I will also do them daily and it is always good to have a reference for when you are stuck.
Thanks man for your such efforts I am a beginner and I have tried starting competitive programming even once before but I gave up due to lack of knowledge and frustration of not improving and remaining stuck....hope to get past this time with your guidance and motivation.
I request to activate ads , your so so so good at teaching , and having thousands of subs , I would happily watch 2 ads at the start and 2 at the end to watch such content
Day 2 - A cute happy number
LOL
I really like the way you present your solutions.
For those who have difficulty understanding this like I had, imagine the integers as a stack in tetris, where same number disappear because of ex-or operation, leaving only the number appearing once.
Very intelligent approach!
Hey @Errichto among all programmer youtuber yours vedio seems best from all,,Keep doing it and take love..You r such a nice man,dude.
errichto, your vidoes are very encouraging
Once you solved it, you can click the 'Solution' button and see the editorial with 4 different approaches and complexities: (1) List operation, (2) Hash Table, (3) Math and (4) Bit Manipulation. The last one is the only one with Space Complexity of O(1).
i add an extra:
- XOR a number with itself *odd number of times* the result is number itself.
- XOR a number *even number of times* with itself, the result is 0.
and because of the associativity and commutativity of XOR operation, Xoring the list of numbers will give you the unique number
I'm a newbie and this helped a LOT!
Errichto has found his RUclips sweet spot.
did you ever felt depressed when you had to see editorials of problems continuously during your beginner's days? Also what did you do for math and numbers theory problems?
Nope. If you continuously need to see editorials, it means you're solving too hard problems.
XOR a number with itself is 0, so the numbers that appear twice in the list will XOR themselves out leaving behind the desired number, the only number without a duplicate.
The same principle applies when you think of it in terms of bit parities.
For each bit of each number in the list, the duplicate bit between two numbers in the list will XOR themselves out to 0, leaving behind the desired bit. If the leftover desired bit is 0, then 0 XOR 0 is 0, if the leftover is 1, then 0 XOR 1 is 1.
Great video. Could you also show the "Submission Detail" (runtime and memory usage) of your solution the next time so I could compare how bad my solution was to yours haha
This question is easy, even I solve this question in 10sec when I see it😂😂 anyway love your content and a lot of love from india
Thank you for those great videos
nice video, learned something new
btw, if you don't want to use extra mem, just edit the first value in the array to xor with everything else
The little bear is disturbing me :)))) I wish you can move it somewhere else , please :D
This is so important for me
Know I going learning that shit bit c++ 💪🏻
you r now motivation for me....
It was so easy for us and it would be hell easy for you 😂
it was hard af for me.
@@konrain7299 pretty sure u could do it in some other way
I think the statement of this problem is a bit vague. Because for the test case [2,1,2,1,4,4,4,4], the expected answer is 0, while from the problem statement, I think it should be 4.
Nicely explained
start this series again!!!!!!
Excellent solution. Thanks for sharing. Do you mind if I asked what would happen if it was string array and they wanted you to find duplicate string? How would you approach to problem ? I do not know answer but I like way you aprroach to problems. That is why I asked.
Bonus question : every number appears twice except two numbers. Find those 2 numbers in linear time and constant space
first find the xor of whole array=n...now partition the array with number having kth bit as 1 and 0.....since now the unique numbers have been seperated..we can apply the same technique individually
@@abhishekdeshmukh7628 that's correct! Kudos!
@@abhishekdeshmukh7628 I actually didnt understand the solution
hoping to see you future videos in python too
Thanks for sharing
Due to this video I have learned ^ operation thaq.
took me some time but i understood after reading the comments 🙂
if in an array exactly1 number is duplicate then how to find it in time complexity of O(n) and space complexity of O(1). Also suggest something other than hash map technique.
Pratyush Kumar you calculate the same XOR sum, then you can use a bitwise AND operator on that value and the same value after applying the logical not operator minus 1. It would look like xorSum &= ~(xorSum - 1) then return xorSum. Edit: here’s the geeks for geeks link where you found this problem www.google.com/amp/s/www.geeksforgeeks.org/find-two-non-repeating-elements-in-an-array-of-repeating-elements/amp/
ruclips.net/video/pKO9UjSeLew/видео.html hope it help
Can you please continue doing this?
Hey ! Can you do them in Java too? It would be awesome!
My confusion is XOR or 2 numbers give another number. For example, if the list of numbers is [4,2,1,2,1], then 4 ^ 3 will result in 7.
Am I missing something?
3 does not appear anywhere in your list of numbers so I don’t know why that is relevant. 4 ^ 2 ^ 1 ^ 2 ^ 1 = 4. That’s all there is to it.
@@psychorameses sorry I meant to write 4^2. Yet again, isn't 4^2 = 6? because in bits 100 ^010 = 110 which is 6. I am little confused why bitwise XOR would return 4 in case of 4^2. I would appreciate clarification
Kamran Badirov Read my comment again. The algorithm is XORing the entire list, not just two numbers. 4 ^ 2 is 6, yes, but 4 ^ 2 ^ 1 ^ 2 ^ 1 is 4.
lets say xor is like addition
a+b+c = c+a+b = b+a+c (that is order wont matter)
in our list
we do
4^2^1^2^1
which can be also written as 4^(2^2)^(1^1)
also a number XORed with itself is zero
=> 4^(0)^(0)
also any number XORed with 0 is the number itself
=> 4 ---> our answer
@@silverzero9524 Thank you very much! That explains a lot!
I thought XORing happens at each iteration of the loop between (4^2) then 6^2 and so on
👌approach
For today's problem,i.e, happy number, I used set to detect cycle, but editorial had a better solution of Floyd cycle detection.
Could someone explain the code at 2:38 ?
what if we have [2,2,2,1] ?
Anyway keep up the good work dude
The question says we would only have one number which does not have a pair so [2,2,2,1] is unlikely test case
@@rutwikhiwalkar9583 thanks I wasn't paying enough attention
Does it still work if the list is not sorted? I thought the list wasn't necessary sorted so I didn't think about this approach. For example, if the array of integers is [10, 12, 10] then at some point the operation would be : 10 ^= 12.
Yes, it still works. Xoring numbers in different order gives the same result
1 1 2 2 3 3 3 3
You output 0, but the answer is 3. I couldn't find it in the problem statement that you either have 1 or 2 occurences of some number.
The statement isn't precise. It should say that the special number occurs exactly once. You can kind of guess it from words "single once" or the title "single number". I didn't even think about it because I just thought: yeah, I know this problem, whatever.
Isn't "every element appears twice except for one" condition enough? If it appears twice, it can't appear 4 times. Am I wrong?
@@alexandercasian4904 No, I'm just saying that the sample in the comment above could be considered valid (all elements except for one occur twice, nothing is stated about the number of occurrences of the exception).
@@МаксимЮрченков-ы5ь Lol, you're right . Well pointed out👍
What to do with parity bit ? If that unique no is even how will I find among all even numbers can u plzz explain 🙂
I want to learn C++ and solving problems, where to start? any suggestion book or course?
are you using only c++ to all the compitition, like code jam and all those??
The total even numbers in the array was 3. So it is obvious that the answer is an even number. And so the least significant bit is 0. But then he considered the second least significant bit. I didn't understand the approach from here. Can anyone please explain it to me?
wtf how its not give an error on line no. 4 there are two semi colon , this is C++ ?
Did you ever try to put two semicolons and try to compile? It isn't an error, you can or many semicolons, almost similarly to making many new lines
@@Errichto ohhh my god 😱😨
I got ur reply thanks for clearing this🙌
I am newbie can you make tutorial coding challange from zero to hero
I'm a beginer, why you use int x = 0 ; ;
I'm confused with the double ' ; '
4:44
its redundant. Its just an empty statement. He did not care to remove it.
thats a typo, he acknowledged it at the end of the video.
it was a mistake
Everybody makes mistakes. Here's a mistake-free crying face ;_;;
@Errichto xor of all number and you go
i just joined codeforces and i was doing this problem of wrong substraction
program.c:3:1: error: unknown type name 'import'
it shows this error
java code
import java.util.Scanner;
public class P {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt() ;
int k= sc.nextInt() ;
for(int i =0;i
Use
import java.util.*;
@@siddharthavyas866 I have imported it well u can see the first line of my code
Did you misspell "70" in "70 ones, 20 zeros, so - one"? Just wanted to ensure that the condition is to have an odd number there.
yup, mispelled. I wanted to say 17.
@@Errichto Oh, makes sense now, thanks. P.S. Glad you started posting new videos more often.
I dunno but I'm kinda bothered at the first problem having that extra semicolon. Or was that intended
I mentioned it at the end ;p
what do you think of the rust language? Many C ++ programmers have switched to rust.
C++ is still best for CP.
Why is this getting compile error ?
class Solution {
public:
int singleNumber(vector& nums) {
int n = nums.size();
for(int i = 0; i < n; i++){
int val = nums[i];
int freq = count(nums.begin(),nums.end(),val);
if(freq > 1){
continue;
}
return val;
}
}
};
please help!
I am unable to understand how doing the XOR is working here. Can someone please explain this to me?
nice
how xor oprtor work in this scene could you explain it
hi, errichto.
should i learn c++ for competitive programming if i already know python?
Yeah, I'm python native and i find out that it isn't enough. C++ can deal with a lot of algorithms easier and faster.
I did not understand the explaination.
How XOR (!=) works that i know but where can i apply it what it returns if i do 4 ^ 5, i just can't get it
I had no idea myself just learned the basics in the past fifteen minutes. I am sharing what I have learned from my observation but I could be wrong.
Convert 4 and 5 to their binary representation which would be 100 and 101 respectively.
Now apply xor operation to corresponding bits.
1 xor 1 becomes 0, 0 xor 0 becomes 0 and 0 xor 1 becomes 1.
What we finally get is 001 which in base 10 is 1.
Therefore 4 xor 5 (also represented as 4^5) should be 1.
Point to note is that for any two numbers in their binary representation like bits become 0 and unlike bits become 1.
This means x^x will become 0 and x^0 becomes x.
Since order doesn't matter in xor, in the above video when numbers are xored in succession, every time a number xors the result it will cancel out its effect if it ever was a part in previous xor steps.
So if you encounter a number twice in an array and you were xorring every element it would be like as if you never encountered a particular number if it presents itself twice in the array.
So if all numbers are repeated only once and a particular number is never repeated we will have that number as the final result.
Hope I was not blatantly wrong with my description but this is what I have gathered from what I read till now.
@@randomrandom316 thanks man, really appreciated
@@amansinhparmar3336 You're welcome :-)
may i know the software(black board) that u have used to explain
It looks like Sublime but I could be wrong
What is your codeforces id name?
try to guess :D
Count zeroes and ones reminds me of codeforces 1220A
What does X ^= a do? What does ^= mean?
Just like a += b is short for a = a + b, here a ^= b means a = a ^ b. And this operator ^ is xor.
fuck this is amazing
Can i get MYSQL problem
Day 2 problem is fun too. Just solved it.
Which language did you use?
@@hemantpatel1413 Java
Can you do it in python ?
Please , please ,please do the second video in python also.....please I really need this.
Congratulations Sir For Qualifying Google Code Jams 2020 Qualification Round . Please Teach Me Competitive Programming . Please I requesting u .
What are saying dude!
Don't put sol at start of video
I take three days to solve it @.@
1111111 how it become a happy number ?
7(1^2)=7-->7^2=49-->4^2+9^2=97-->9^2+7^2=130-->1^2+3^2+0^2=10-->1^2+0^2=1 :)
@@tejakumar586 Thnaks bro
Then what about 2?
en.m.wikipedia.org/wiki/Happy_number
N=1 and n= 7 are happy numbers below 9
@@arunp9437 2^2=4-->4^2=16-->1^2+6^2=37-->3^2+7^2=58-->5^2+8^2=89-->8^2+9^2=145-->1^2+4^2+5^2=42-->4^2+2^2=20-->2^2+0^2=4(here we get into the loop,because already after 2 we have got 4), so it never evaluates to 1.Hence, not a happy number.
Siema !!!
#Errichtojourney day1
I think that's april joke
wow....i did by unorderd_set and i feel like im dumb and intelligent at the same time....
i also solve this ques using XOR
bro you can find the tutorial on geeksforgeeks
@@iitnakanpur.. Yes C ++ fork
@John Smith suppose you have array=[1,2,4,2,1]
1^2^4^2^1
=(1^1)^(2^2)^4
=0^0^4
= 4
@Vishal Belbase xor same no is zero ie 1^1=0 and xor of no. with zero is no 1^0 =1
@@bakaSenpai890 hey what will be 1^2?
Hey
gmail inbox: 6021
😂😂😂😂what the
Bye
Polak, xD