This one is fun: Find the unique number in an array. For example arr = [2, 4, 3, 5, 1, 4, 2, 1, 5] where 3 is the unique number. Solution: arr.reduce((a, b) => a^b) This works if there are an odd number of occurrences of the unique number and an even number of occurrences of all other numbers. When you XOR all the numbers in the array, the even occurrences of the repeated numbers will cancel each other out (since x ^ x = 0), and you will be left with the unique number (since it only occurs once).
I have seen the complete lecture & it was amazing . The way of delivering concepts was top Notch , video & audio quality . Your content deserves more reach. Thanks for the Concepts brother. Respect++;
It would be really helpful if you would make a video on how to apply binary search technique to solve hard cp problems sometimes it happens that we might not even know that the problem involves binary search. Btw this one is again awsome and great video on bits👍
Knowing the problem involves binary search is the hardest part, generally look for clues like minimize maximize, maybe this helps, recent div3 E question involved binary search, and I was so happy it clicked to me. dopamine.
17:08 actually, can swap two numbers without using temporary variable without xor. suppose two numbers x and y now let x = x-y y = y+x ( y + x-y = x) x = y - x = (x - x +y) x and y are now swapped.
see the problem with this is overflow issue X+Y can sometimes be more than "long long int " say we needed to swap X = 1e18 and Y = 1e18 (yeah ik its same...but think user input was this and u dint knw both are same) now ur code fails ^ code works fine for all there are * and / to do the same thing u did but ^ way is best and can handel all the cases
Please make more videos like DIFFERENCE ARRAY TECHNIQUE, (yesterday's vid), i have stuck many times on same type of questions/ questions which use similar concepts and we are just unable to optimise the code... also thanks for everything
Trick 9 is garbage. Use this identity only if you encounter rhs part somewhere, to transform back to A + B. How can a simple arithmetic operation which even has a cpu instruction for it (ie. ADD instruction), be slower than writing some hob nob like (A^B)+2*(A&B) or (A|B)+(A&B). Priyansh is trying to say us that we should opt for an operation consisting of a bitwise or, and, along with an "add" to replace a simple ADD operation. How idiotic isn't it. For the first identity, it also needs you to multiply with two as well. Simply slow because instead of doing one operation we're doing 3-4 extra operations.
Just if something works mathematically, doesn't mean that going that alternative route is going to be faster. This is only learned through practice, and people who are aware of this, won't give out such tips without a 'gotcha'. Giving this information is good. But it should also be accompanied by a disclaimer that using this would make your code slow instead of fast. He says this in the intro of this video that bitwise operations are faster. People are going to take his word for it due his immense influence and popularity, but this is wrong.
According to my benchmarks The first version is the most slow, (140796ns) 2nd version is a bit better than the first, but still slow, (1146ns) 3rd version is the fastest of all of them (108ns)
#include #include int Add1(int a, int b); int Add2(int a, int b); int AddNormal(int a, int b); constexpr int numIters = (int) 1e9; class Timer { public: using NanoSeconds = std::chrono::nanoseconds; public: Timer(std::chrono::nanoseconds& runtimeRef, bool shouldAlsoPrint = false) :m_RuntimeRefToReturn(runtimeRef) ,m_ShouldPrint(shouldAlsoPrint) { start = std::chrono::system_clock::now(); } ~Timer() { m_RuntimeRefToReturn = std::chrono::system_clock::now() - start;
Guys in trick 06 use XOR instead od AND beacuse it gives you a wrong swape here is an example: Initial values: X = 2 (binary: 10) Y = 3 (binary: 11) X = X AND Y (10 AND 11): X = 10 AND 11 = 10 (decimal: 2) Y = X AND Y (10 AND 11): Y = 10 AND 11 = 10 (decimal: 2) X = X AND Y (10 AND 10): X = 10 AND 10 = 10 (decimal: 2) see its not swaping correctly! but when you use XOR it will swape the values perfectly!
When does TLE eliminators batch start after September? I'd like to join after my placements Checking if a number is a power of 2 Swapping two numbers Manipulating kth bit Counting set bits These were super useful to me. Thanks a lot vro ! Btw, whenever I give contests, I feel really hard to solve Bit manipulation problems. I can't even build up the intuition. Can you post long video about Bit manips covering the stuff needed for CP other than basics? It'd be really helpful
This is extremely helpful. One of the best videos on bit manipulation.
I was in problem about the bitwise operator but now I found the solution
Thankyou very much
Good video! The lecture is straightforward and easy to understand!
literally the best bitwise video, clear and straight to the point, thanks a lot.
That was good info in a short and concise video . Loved it !
This one is fun:
Find the unique number in an array. For example arr = [2, 4, 3, 5, 1, 4, 2, 1, 5] where 3 is the unique number.
Solution:
arr.reduce((a, b) => a^b)
This works if there are an odd number of occurrences of the unique number and an even number of occurrences of all other numbers. When you XOR all the numbers in the array, the even occurrences of the repeated numbers will cancel each other out (since x ^ x = 0), and you will be left with the unique number (since it only occurs once).
I have seen the complete lecture & it was amazing .
The way of delivering concepts was top Notch , video & audio quality .
Your content deserves more reach.
Thanks for the Concepts brother.
Respect++;
It would be really helpful if you would make a video on how to apply binary search technique to solve hard cp problems sometimes it happens that we might not even know that the problem involves binary search.
Btw this one is again awsome and great video on bits👍
Knowing the problem involves binary search is the hardest part, generally look for clues like minimize maximize, maybe this helps, recent div3 E question involved binary search, and I was so happy it clicked to me. dopamine.
That interview problem right🤔
@@shri9229 thanks for the tip hoping to apply soon
For 10th trick in java there is a similar function to count setbit
For integer x it is Integer.bitCount(x) and for long it is Long.bitCount(x).
Watched half of it and liked it, let me come back when I finish the basic DSA part
I knew the first one ,but others are also cool as hell. Really like this video.
hell is not cool btw
This is really insane.Really helpful.
Very useful video..I felt bitwise operations as tough topic. You have made it easy now. Thank u
Please upload videos like this, a few tips and tricks in competitive programming and related techniques.
17:08 actually, can swap two numbers without using temporary variable without xor.
suppose two numbers x and y
now let x = x-y
y = y+x ( y + x-y = x)
x = y - x = (x - x +y)
x and y are now swapped.
You can also write
X = X+Y;
Y = X-Y;
X = X-Y;
@@adityarupda1795 yes 👍
see the problem with this is overflow issue
X+Y can sometimes be more than "long long int "
say we needed to swap
X = 1e18 and Y = 1e18 (yeah ik its same...but think user input was this and u dint knw both are same)
now ur code fails
^ code works fine for all
there are * and / to do the same thing u did
but ^ way is best and can handel all the cases
Everything😊😊
Great explanation, in simple examples
the bin function looks like sin function 😂
🤣🤣 And, & looks like a yoga position 😉
Bc meri toh fatt gayi thi , sin kabse agya
Really great video, mad respect for you!
great sir thank you
awesome video, thanks!
Please make more videos like DIFFERENCE ARRAY TECHNIQUE, (yesterday's vid), i have stuck many times on same type of questions/ questions which use similar concepts and we are just unable to optimise the code... also thanks for everything
It was really helpful. Thank you for such a video and good explanation👍👍.
Helpful 👌
Thanks a lot! this was very helpful.
thank you for this video sir....
I just now saw this video . I am regretting why I didn't see this before 😢. It's really useful. Thank you .
Same
Nothing to say about you,,you are awesome
Thanks. Super good!
Last few tricks are amazing.
Can we have a video on Number theory tricks that can be very useful. I stuck a lot on basic Number Theory problems.
Trick 9 is garbage. Use this identity only if you encounter rhs part somewhere, to transform back to A + B.
How can a simple arithmetic operation which even has a cpu instruction for it (ie. ADD instruction), be slower than writing some hob nob like (A^B)+2*(A&B) or (A|B)+(A&B). Priyansh is trying to say us that we should opt for an operation consisting of a bitwise or, and, along with an "add" to replace a simple ADD operation. How idiotic isn't it. For the first identity, it also needs you to multiply with two as well. Simply slow because instead of doing one operation we're doing 3-4 extra operations.
Just if something works mathematically, doesn't mean that going that alternative route is going to be faster. This is only learned through practice, and people who are aware of this, won't give out such tips without a 'gotcha'. Giving this information is good. But it should also be accompanied by a disclaimer that using this would make your code slow instead of fast. He says this in the intro of this video that bitwise operations are faster. People are going to take his word for it due his immense influence and popularity, but this is wrong.
According to my benchmarks
The first version is the most slow, (140796ns)
2nd version is a bit better than the first, but still slow, (1146ns)
3rd version is the fastest of all of them (108ns)
Here is the benchmark code
#include
#include
int Add1(int a, int b);
int Add2(int a, int b);
int AddNormal(int a, int b);
constexpr int numIters = (int) 1e9;
class Timer
{
public:
using NanoSeconds = std::chrono::nanoseconds;
public:
Timer(std::chrono::nanoseconds& runtimeRef, bool shouldAlsoPrint = false)
:m_RuntimeRefToReturn(runtimeRef)
,m_ShouldPrint(shouldAlsoPrint)
{
start = std::chrono::system_clock::now();
}
~Timer()
{
m_RuntimeRefToReturn = std::chrono::system_clock::now() - start;
if (m_ShouldPrint)
std::cout
very nice explanation
NICE SUPER EXCELLENT MOTIVATED
bro i am your big fan i love you bro i like your coding skills and i follow you too
Awesome tricks!
Great video !
Thank you
please post pt2 !!
Very useful one
Thank you vaiya.
Hi, a very popular problem with bitwise is when all the numbers appear 3 times except 1, can you please make a detailed video for the same.
Thanks!
Which note taking apps do you use???
thanks:)
awesome man
in the third trick the last one i didnt understand what you said and how it write you mean not of all the bits but how?
Man the last one was new to me found it more usefull.Try to make more usefull videos ilke this.
i need 1st vedio link
23:02 eureka moment for me.
A+b trick again you are doing addition after or and & operations
Guys in trick 06 use XOR instead od AND beacuse it gives you a wrong swape here is an example: Initial values:
X = 2 (binary: 10)
Y = 3 (binary: 11)
X = X AND Y (10 AND 11):
X = 10 AND 11 = 10 (decimal: 2)
Y = X AND Y (10 AND 11):
Y = 10 AND 11 = 10 (decimal: 2)
X = X AND Y (10 AND 10):
X = 10 AND 10 = 10 (decimal: 2)
see its not swaping correctly! but when you use XOR it will swape the values perfectly!
bro watch the video once again where he told you to use AND. he is only using XOR in all three steps
I liked trick 8 more than others
xor swap trick ques was asked in ICPC Amritapuri Qualifiers.
really ?
which year ??
if u are talking abt XOR sort of 2022
nah bro...that question was completely diff 😂😂
@@codecorn8030 i did it my xor swap approach only.
bro try to run one program on each trick as an example
When will tle eliminator next batch is going to start???
July last week
8:04 The formula to toggle the Kth bit is x^(1
When does TLE eliminators batch start after September? I'd like to join after my placements
Checking if a number is a power of 2
Swapping two numbers
Manipulating kth bit
Counting set bits
These were super useful to me. Thanks a lot vro !
Btw, whenever I give contests, I feel really hard to solve Bit manipulation problems. I can't even build up the intuition. Can you post long video about Bit manips covering the stuff needed for CP other than basics? It'd be really helpful
very good explanation easy to understand but inside video is annoying
same video with animation on Log2base2.
where is part1??
ruclips.net/video/96RG7EBF8LI/видео.html
I think I might actually win my competition now! best trick were: odd or even, and divide and multiply with 2^k
Trick 8 is not exactly correct, and wont be good to use for some problems because it will return unexpected result if x is neither a nor b.
Sin😂😂😂bin
Wan zero wan hahahhaa
can you just slow down a bit? smh
Why can't I understand anything
Maybe you should start using bit operations a lil more in your code
bro i am your big fan i love you bro i like your coding skills and i follow you too