Majority element in an array | Bitmasking

This video explains a very frequently asked interview question which is to find the majority element in an array. I have concentrated on explaining the bitmasking approach to find the majority element in an array, which is one the efficient methods to do so. First i have explained the method and then the CODE and at last i have explained the TIME & SPACE complexity. So, do watch the video till the end to get a good grasp on the problem. As usual, CODE LINK is present below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.com/SuryaPratapK/...
==========================================================
Check if Kth bit is SET: • Check if Kth bit is se...

[@the3idiots787]

This explanation is mindblowing. Can't imagine that I understand it in one attempt.

[@techdose4u]

Nice :)

[@ShaliniNegi24]

Whenever I find a solution to any problem by Tech Does my happiness level increases, thank you. keep it up:)

[@techdose4u]

Thanks :)

[@degavathanandnayak9692]

I absolutely love the way you teach...It is easy to grasp the concept, Thank you so much, brother!!

[@techdose4u]

Welcome :)

[@klausdupont6335]

A great illustrative explanation!

[@awakashsinha9926]

Now I m happy eventually channel goes up ,keep up good content

[@techdose4u]

:) yea

[@sandeepnallala48]

awesome technique sir:) most underrated channel sir... love your vedios sir : )

[@techdose4u]

Thanks :)

[@sarfarazalam6077]

Great explanation, appreciate your effort. Thank you :)

[@techdose4u]

Thanks :)

[@thinkopedia191]

Try to use Boyer moore voting algorithm in this question to solve in O(n) time

[@ShreyaSingh-vr9qi]

Nicely explained, nice approach . Thanks a lot for your effort in making wonderful tutorials. Request you to start with tutorials of Codeforces too...........

[@techdose4u]

Wait man. I have not covered many basic topics and DS. After I am finished with basic stuffs, I will move to harder topics. I don't want to randomly jump to topics.

[@amanvijayvargiya3468]

I am so happy to subscribe your channel...great explanation

[@techdose4u]

Thanks :)

[@mystryb345]

Bro your every topic explanation is quite good..Keep it up

[@techdose4u]

Thanks bro

[@hardikraj9469]

A really great solution :)

[@techdose4u]

Thanks :)

[@VarsneyaSrinivas]

Subscribed ❤

[@rncsMahimaMahendru]

amazing!!!!

[@praveenj3112]

Great explanation and I understood

[@techdose4u]

Nice

[@sairamgourishetty]

Great explanation sir

[@techdose4u]

Thanks :)

[@prapulkrishna]

Brilliant Solution

[@techdose4u]

Thanks :)

[@Yash-uk8ib]

nice video sirr.....

[@techdose4u]

Thanks :)

[@rohanprak]

time complexity is O(32*n + 32+ n) { getting 32 bits , checking probable bits , verifing ) so effectively it is O(n) isn't it ?

[@techdose4u]

Yes it is O(N)

[@utkarshgupta2909]

More logical approach here is any 1 of them : 1 or 0 are in majority. That will be the result for that column. if count! > n/2 then 1 else 0. Just a diff way of saying

[@shubh0000071]

Do check moore voting algo as it gives linear time solution to this

[@techdose4u]

:)

[@ganeshkamath89]

Is this method faster than 1) counting sort 2)using quick sort and keeping track of highest subsequent numbers 3) Using Hash table to count elements?

[@solveunsolvable1024]

@techdose using a dictionary and note the frequency of all the elements by traversing only once and then later on by traversing the dictionary and checking whether the value of the key is >n/2 or not ...isn't this a optimised approach?

[@Killer-gn5xw]

Even I had the same question!!

[@alexandruteodor3585]

Hi! Would you explain line 19 please?. I looked at the video in the description and I also don't understand line 22 from there, if (n & mask). Thank you!

[@younisthetrainer8461]

If() return boolean values but it telling count++;

[@HimanshuSingh-ob9qo]

🙏👍

[@techdose4u]

👍

[@rajatnagpure7445]

int majorityElement(vector& nums) { map cnt; int max=INT_MIN,res; for(int i=0;isecond>max){ max=itr->second; res=itr->first; } } return res; } This question can be solved this way too! why would u prefer bit masking solution over this?

[@techdose4u]

Just to show how to solve using BitMasking.

[@rogerknight8447]

Is unordered_map (number,count) way can b another method. Fir the same TC but SC wld b O(N)

[@techdose4u]

??

[@rogerknight8447]

@@techdose4u can we count the number of elements using map data structure As map mp Where mp.first() is the particular element inside query array And mp.second() as its count And is this possible in O(N) time complexity??

[@stonecoldcold2941]

Yes it can be

[@shaswatdas6553]

Why can't we use hashing? It would do in one traversal but takes more space

[@techdose4u]

Yes you can do it.

[@yashpreetbathla4653]

sir it will not work for n/3 element what to do for that?

[@techdose4u]

Actually for a case of N/3, N/4....N/K, there can be many possible elements. If you have a specific problem then pet me know. This was for N/2 only.

[@karanaggarwal8456]

Can we use moore voting algorithm??

[@techdose4u]

Yes

[@klausdupont6335]

The complexity is a bit lossy. The number of bits is quite impossible to be equal to the number of elements in the array; actually, the number of bits in general cases is way less than the number of elements. A more precise complexity would be O(a * log(n)), where a is a relatively quite small number (in modern days it should be from 8-64, or at most 128), and n the size of the array. In general it is closer to O(logN) rather than O(NlogN).

[@yashwindevadiga4545]

Hi Sir, Is this the optimal solution or the solution to solve the problem using bitmasking? Can you please confirm?

[@BharatTheGreat1]

Noo this is not most optimal

[@dovyraj1272]

MOORE VOTING ALGORITHM

[@bhanukumargorle1761]

Is it working for negative numbers?

[@bhanukumargorle1761]

I'm getting wrong answer when majority number is negative

[@techdose4u]

Dint check it for negative nos.

[@HimanshuSharma-tm2ms]

yes logically it is working because negative numbers will be written in 2's complement form and the same procedure gives me the result.

[@techdose4u]

Can you share the code if possible.

[@maddinenisruthi2753]

@@techdose4u code def majorityElement(self, nums: List[int]) -> int: va = 32 no = 0 for j in range(va): count = 0 for k in nums: if k&(1

[@yashpreetbathla4653]

Sir ye isme to fail hojayegi trick... [2,1,2,5,3,2]

[@techdose4u]

This array does not have any majority element. 2 is only occuring N/2 times but this trick is for finding element occuring >N/2 times.

[@yashpreetbathla4653]

@@techdose4u ok ok sir i got it! what to do if find >=n/2

[@kamleshsaini5474]

Sir, what about this array [1 1 3 3 4 4 4]. I think according to your explanation ans would be 1 but ans should be 4. Please correct me if am going wrong.

[@kumarkashyap3996]

there is no any majority element

[@kumarkashyap3996]

using bitmasking gives 1 then we must verify weather that element is majority element or not

[@kamleshsaini5474]

@@kumarkashyap3996 okk got it

[@helloworld6679]

Time complexity does not seem correct, proper time complexity = O(log(maximum)*N) or O(32*N) or O(N) if maximum number can be represented in 32 bits , here N is the number of elements (array length). When you used NlogN then you use N as a the array length as well as the maximum valued number

[@techdose4u]

Yea.....when i calculated time then i made use of (log N base 2) denoting the number of bits which can represent the Max number N and the N which was multiplied is no of array elements. If the representation is dense (with low gaps) then both N will be same. If it's sparse then it will be 32N or 64N etc. You understood the correct version of it :)