2-8 lines Bit-Counting


  • 3

    I've seen several high-voted bit-counter solutions, but they were all quite long.

    C++ (Java would be almost the same)

    int majorityElement(vector<int>& nums) {
        int winner = 0;
        for (int i=0; i<32; i++) {
            int ones = 0;
            for (int n : nums)
                ones += (n >> i) & 1;
            winner += (ones > nums.size() / 2) << i;
        }
        return winner;
    }
    

    Python

    For once, Python's arbitrarily large integers are a disadvantage :-(

    def majorityElement(self, nums):
        return (sum((sum(n>>i&1 for n in nums) > len(nums)/2) << i
                    for i in range(32)) + 2**31) % 2**32 - 2**31

  • 0
    N

    The above solution fails for the case [8,9,10]. In this case, 100,101,110 has 1's in the msb. On evaluating each and every bit, it fails. Please correct me if I am wrong.

    Thanks!


  • 0

    Your array has no majority element and is thus invalid.


  • 0
    O

    @StefanPochmann Pretty much the same with this. Slightly shorter.

    return sum([-2**31,1<<i][i<31] for i in range(32) if sum((n>>i)&1 for n in nums)>len(nums)/2)
    
    return sum(1<<i if i<31 else -2**31 for i in range(32) if sum((n>>i)&1 for n in nums)>len(nums)/2)
    

  • 0
    C

    Hi big god Stefan,Could you explain these code?
    '''
    ones += (n >> i) & 1;
    winner += (ones > nums.size() / 2) << i;
    '''


  • 0
    E

    @cdhunter829
    If you are having difficulty understanding operations done in these two lines you should read upon "Bitwise operators" and "Compound assignments" in c++.


  • 1
    L

    @cdhunter829

    For your questions.
    I added some comments to big god Stefan's original source code.
    GL!

    class Solution {
    public:
    	int majorityElement(vector<int>& nums) {
    		int answer= 0;
    		
    		for (int i=0; i<32; i++) {
    			int ones = 0;
    
    			//count `1`s of the i-th bit of all given numbers
    			for (int n : nums) {
    				ones += (n >> i) & 1;
    			}
    
    			//put `1` to the i-th bit of answer if `1` is the majority of the i-th bit of each number
    			answer += (ones > nums.size() / 2) << i;
    		}
    		return answer;
    	}
    };
    

  • 0
    N
    This post is deleted!

  • 0
    N

    @StefanPochmann good job, and it's one perfect solution! Also quite easy to read and understand for us starting the programming journey here. I only have one concern, and how about the time complexity and space complexity? seems it will throw out the error - Time Limit Exceeds sometimes? Looks forward to your reply, thanks a lot


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.