JAVA--------------Easy Version To UnderStand!!!!!!!!!!!!!!!!!!!


  • 18
    H
    	public static int singleNumber(int[] nums) {
    	int len = nums.length, result = 0;
    	for (int i = 0; i < 32; i++) {
    		int sum = 0;
    		for (int j = 0; j < len; j++) {
    			sum += (nums[j] >> i) & 1;
    		}
    		result |= (sum % 3) << i;
    	}
    	return result;
    }

  • 2
    G

    This is a nice and neat solution, but could you kindly explain how do you handle negative value? I'm trying to rewrite your solution into python and I'm failing on negative test cases.

    def singleNumber(nums):
        res = 0
        for i in range(32):
            count = 0
            for n in nums:
                count += (n >> i) & 1
            res |= (count % 3) << i
        return res
    

    Edit: I solved it by handling the negative case as below:

    def singleNumber(nums):
        res = 0
        for i in range(32):
            count = 0
            for n in nums:
                count += (n >> i) & 1
            rem = count % 3
            if i == 31 and rem:  # must handle the negative case
                res -= 1 << 31
            else:
                res |= rem << i
        return res
    

    I don't know why in your case it's not failing, probably because of Java?


  • 0
    G
    This post is deleted!

  • 0
    H

    sorry,i am not familiar with Python!


  • 0
    B

    I'm not an expert on bit manipulation by any means.

    But I could hypothesize that in Python the '>>' operator acts on unsigned ints, whereas in Java '>>' acts on signed ints and '>>>' acts on unsigned ints.


  • 0
    H

    It is because Java ints have 32 bits, but python numbers have "infinite" bits:

    https://wiki.python.org/moin/BitwiseOperators

    So, the Java answer just has to recreate a finite 32-bit pattern, whereas a python answer has to make one that is infinite.


  • 3
    C

    I don't quite understand this solution, especially this part: "(sum % 3) << i". What does the (sum % 3) do ? Can someone explain a bit? Thanks!


  • 1
    B

    The solution is checking to see how many times a bit is on at a particular position and saving it in the sum variable. Since each number appears three times, except for the one we are looking for then sum % 3 will tell us if the the bit at that location should be on for the number that appears only once.

    For example, for every number that appears only three times and doesn't share a bit with the number we are looking for the sum will be 3 at that location and the sum % 3 will be 0. If the number that appears once does share a bit at this location with others then sum must be some multiple of 3 plus 1. Since every other number appears three times then sum must be some number n * 3 plus 1 if the number we are searching for shares a bit as well. Thus, sum % 3 will always be 0 or 1.

    The left shift, just moves the bit back into its proper place to be added to result. Since we right shifted the bit, we have to left shift it again before inserting it into result.

    So for example, lets say we have an array with [3, 3, 3, 1], the bits look like:
    0111
    0111
    0111
    0001

    For each iteration of the loop:
    i = 0, sum = 4, sum % 3 = 1
    result = 1
    i = 1, sum = 3, sum % 3 = 0
    result = 1
    i = 2, sum = 3, sum % 3 = 0
    result = 1
    i = 3, sum =3, sum % 3 = 0
    result = 1

    We then return 1 as the result.


  • 0
    Z

    COOL!!!!!!!!!!!!!!!!!


  • 0
    S

    How does this solution behaves when the number that is not three times is present 3*n times?

    As I see it, this algorithm would not catch that case.


Log in to reply
 

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