Java O(n) easy to understand solution, easily extended to any times of occurance


  • 192
    Y

    The usual bit manipulation code is bit hard to get and replicate. I like to think about the number in 32 bits and just count how many 1s are there in each bit, and sum %= 3 will clear it once it reaches 3. After running for all the numbers for each bit, if we have a 1, then that 1 belongs to the single number, we can simply move it back to its spot by doing ans |= sum << i;

    This has complexity of O(32n), which is essentially O(n) and very easy to think and implement. Plus, you get a general solution for any times of occurrence. Say all the numbers have 5 times, just do sum %= 5.

    public int singleNumber(int[] nums) {
        int ans = 0;
        for(int i = 0; i < 32; i++) {
            int sum = 0;
            for(int j = 0; j < nums.length; j++) {
                if(((nums[j] >> i) & 1) == 1) {
                    sum++;
                    sum %= 3;
                }
            }
            if(sum != 0) {
                ans |= sum << i;
            }
        }
        return ans;
    }

  • 4
    G

    God! this is brilliant !!!!!!
    ................


  • 0
    L

    This solution is really awesome


  • 0
    F

    Awesome +1........


  • 18
    L
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int i = 0; i < 32; i++){
            int sum = 0;
            for(int n: nums)
                if((n >> i & 1) == 1)
                    sum++;
            sum %= 3;
            res |= sum<<i;
        }
        return res;
    }
    

    Brilliant idea! I have two suggestions:

    1. move sum %= 3 out of the inner loop to reduce the module operation.
    2. remove the condition check ( sum != 0).

  • 1
    V

    Well i had a similar approach, but what if a target number occurs a number (say, k)times and the number(i.e k) occurs a multiple of 3 times(i.e. k = 3*n).


  • 4
    T

    Great solution! But I think this solution will not be correct if there is a number appeared two times, like[1,1,1,2,2,2,3,3]. It will return 6, instead of 3. This solution works for the number whose occurrences % 3 is 1. To make it work for this case,

    public int singleNumber(int[] nums) {
        int ans = 0;
        for(int i = 0; i < 32; i++) {
            int sum = 0;
            for(int j = 0; j < nums.length; j++) {
                if(((nums[j] >> i) & 1) == 1) {
                    sum++;
                    sum %= 3;
                }
            }
            if(sum == 1) {
                ans |= sum << i;
            }
            if(sum == 2) {
                ans |= sum/2 << i
            }
        }
        return ans;
    }
    

    But this will depend the author's purpose of general solution.


  • 3
    Y

    I don't think this will work if a number appears multiple of 3 times.


  • 0
    H

    What a brilliant idea!!!!!!!


  • 0
    W

    Brlliant ! Thanks !


  • 2
    M

    @touchdown

    Why not just do
    ans |= (1 << i)


  • 0
    J
    This post is deleted!

  • 0

  • 1
    W

    @chidong This solution relies on the sum of the bits to not be a multiple of 3 because it checks against the remainder of mod3 and if the frequency of the "single" number is a multiple of 3, then the remainder is 0, so the code will not set any bits. It's a great solution given the assumption that the "single" number doesn't occur in a multiple of 3.


  • 0

    @wilchang You are actually mis-understanding this. The "number" you are talking about it not integer. It is actually bit, 0 or 1. There is no such scenario of multiple of3. The algorithm first breaks each number into 32 bits, and then consider and add all numbers (bits, not integers) bit by bit. See this part: "(n >> i & 1)".

    You can try to run this test case: [9,9,9,6]


  • 1
    W

    @chidong try the use case of 1,1,1,4,4,4,4,4,4. Since the bit at the third position (4=100) is repeated as a multiple of three times, it isn't considered since we check sum%=3. Per the description, all elements are repeated 3 times except one, which in this case is 4, repeated six times, a multiple of 3.


  • 0

    @wilchang where is your "single number" then..........?


  • 1
    W

    @chidong the problem description is:
    Given an array of integers, every element appears three times except for one. Find that single one.
    We are to solve the problems by the description acceptance criteria. The single number is the number not repeated three times. In my example of 1,1,1,4,4,4,4,4,4: the "single number" not repeated exactly three times is 4, as 4 is repeated six times and 1 is repeated three times. Single number refers to the element that is repeated not three times.


  • 0

    @wilchang No.. it's not. SINGLE number. Try to run your [1,1,1,4,4,4,4,4,4], gives -1 as the official answer, not 4.


  • 2
    W

    @chidong I think either the problem description should be updated to ask for a number not repeated at all compared to every other element repeated three times or the accepted solution to what it is asking for, which is a single number not repeated three times, and every other number repeated three times. The description literally means just one element is not repeated three times.


Log in to reply
 

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