O(n) time O(1) space Java code

  • 2


    Suppose C = A ^ B, then the 1 bits in C are exactly the ones that only exist in either A or B (C cannot be 0 or A and B would be the same). It is because all other elements appearing twice are turned into 0 during the XOR process. The XOR result C is actually the XOR of the only two elements each appearing once.

    Thus, for whichever 1 bit in C, "having it or not" can be the condition for dividing those elements into Group A(which containing A) and Group B (which containing B). As per to the explanation above, the XOR result of those elements in Group A (except for A) would be 0, and the XOR of all elements in Group A would be A. It's the same story in Group B.

    Java Code

    public class Solution {
        public int[] singleNumber(int[] nums) {
            int c = 0;
            for (int num : nums) {
                c ^= num;
            // get the lowest "1" bit of C
            c &= -c;
            // rets[0], rets[1] would be the XOR results of Group A and Group B
            int[] rets = new int[2];
            for (int num : nums) {
                if ((num & c) == 0) {
                    rets[0] ^= num;
                else {
                    rets[1] ^= num;
            return rets;

    How to get the lowest 1 bit of C
    For a positive integer C, -C would be stored as 2's complement of C and with the highest bit (sign bit) set to 1. To compute the 2's complement of an integer, simply keep the trailing 0s and the lowest 1 bit unchanged, and then revert all the higher bits. So, C & (-C) would be the lowest 1 bit of C.

Log in to reply

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