Share my solution [Java] - Count bits


  • 68

    Definitely not the fastest solution but I post it here for your reference since it's different from the rest I saw. The problem reminded me of the approach I followed at Single Number II (problem 137).

    We can iterate over the bits of all numbers and for every position find out if ones outnumber the zeros (among all numbers). If this is the case, the corresponding bit of the ret variable (which holds the result) is set. We essentially "construct" the number we look for.

    The following code is simple and should be easy to understand.

    public int majorityElement(int[] num) {
    
        int ret = 0;
    
        for (int i = 0; i < 32; i++) {
    
            int ones = 0, zeros = 0;
    
            for (int j = 0; j < num.length; j++) {
                if ((num[j] & (1 << i)) != 0) {
                    ++ones;
                }
                else
                    ++zeros;
            }
    
            if (ones > zeros)
                ret |= (1 << i);
        }
        
        return ret;
    }

  • 0
    S

    This is a nice alternative. As you have already noted it's not faster though, but kudos for implementing it.


  • -11
    W

    That is a very smart approach.


  • 0
    J

    can you explain why i is range in (1-32) but need "1L"(long type)?


  • 0
    T

    This is one of most easy-to-understand solutions for this problem. Small modifications could be made to make it a little more streamlined:

    • Instead of having a separate 'zeros' variable, we just use the 'ones' variable; compare whether that is greater than half of the number. Something like if(ones > (num.length >> 1)) should do the trick.
    • Instead of the conditional if ((num[j] & (1 << i)) != 0) { ++ones; }
      one could just replace it with ones += ((num[j] >> i) & 1);.

    Great solution overall, though. Easy to understand, not much arcane bit-twiddling.


  • 0
    J

    very easy to understand!!!


Log in to reply
 

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