My Java solution adapted from the commonest solution here


  • 34
    H

    I read @zhiqing_xiao 's post to get an idea about the solution. His solution is really smart and elegant, but it took me a while to get understand how "diff &= -diff" works. I changed it a little bit to make it better understood, but it is totally based on his solution.

    Instead of using the right-most "1" of diff, I used the left-most "1" to divide groups. This should also do the trick.

    public class Solution {
    public int[] singleNumber(int[] nums) {
        int diff = 0;
        for(int num: nums){
            diff^=num;
        }
        diff = Integer.highestOneBit(diff);
        
        int[] result = new int[2];
        Arrays.fill(result,0);
        for(int num: nums){
            if((diff & num) == 0){
                result[0] ^= num;
            }
            else{
                result[1] ^= num;
            }
        }
        return result;
    }
    

    }


  • 0
    Z

    Elegant solution. Can you please explain more why the highest one bit could do the trick and how the next loop works?


  • 0
    S
    1. why the highest one bit?: You can take any bit. The idea is to divide all the numbers in two groups such that for one group the selected bit is 1 and for the another the selected bit is 0.

    2. how the next loop works? : Integer.highestOneBit(diff) updates the diff to a number with only one bit set. In the nums {1,2,1,3,2,5}, diff is changed from 110 to 100. Now, in thee for loop, you are dividing the numbers for which first bit is set and not set. This separates our two given numbers also. Now you do the Single Number 1 approach here on both the groups. :)


  • 0
    Z

    Clear enough. Brilliant!


  • 0
    P

    +1 for highestOneBit method!


Log in to reply
 

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