A general C++ solution for these type problems


  • 80

    There are so many brilliant solutions for this problem used "| & ^ ~", and I have learned a lot from these solutions. Here is a general solution for who not familiar with "| & ^ ~".

    Q: Most elements appeared k times, except one. Find this "one".

       int singleNumber(vector<int>& s) 
        {
        	vector<int> t(32);////Made a array contain 32 elements.
        	int sz = s.size();
        	int i, j, n;
        	for (i = 0; i < sz; ++i)
        	{
        		n = s[i];
        		for (j = 31; j >= 0; --j)
        		{
        			t[j] += n & 1;//Find the last digit.
        			n >>= 1;
        			if (!n)
        				break;
        	    }
            }
    	int res = 0;
    	for (j = 31; j >= 0; --j)
    	{
    		n = t[j] % 3;//"3" represents k times. 
    		if (n)
    			res += 1 << (31 - j);
    	}
    	return res;
    }

  • 6
    S
    int singleNumber(vector<int>& nums) {
            int one = 0, two = 0, three = 0;
            for (int i = 0; i < nums.size(); ++i) {
                two |= one & nums[i];
                one ^= nums[i];
                three = one & two;
                one = one ^ three;
                two = two ^ three;
            }
            return one;
        }

  • 0
    Y

    smart solution.


  • 0
    G

    Beautiful !!!!


  • 0
    F

    It's smart, however, the question requires "Could you implement it without using extra memory"?


  • 0
    Y

    The extra memory used is constant, that should be allowed.


  • 0
    S

    I also try to solve problem in general case, and was surprised by bit solutions.

    I have problems with negative int, so I convert all to long long. There is my solution:
    Main idea is calculate all in ternary system.

    class Solution {
    public:
        int singleNumber(vector<int>& nums) {
            long long  answer = 0;
            for (auto& n : nums) {
                long long rank = 1;
                long long num = n + 1e10;
                while (num / rank) {
                    answer += rank * ((num / rank + answer / rank) % 3 - answer / rank % 3);
                    rank *= 3;
                }
            }
            return answer - 1e10;
        }
    };

  • 0
    S

    This "Could you implement it without using extra memory"? means that you must use constant space. (I don't now any solution without new constant). And author use constant space nearly 40 elements.


  • 1
    A

    I did the same thing using Java:

    public class Solution {
        public int singleNumber(int[] nums) {
            int[] count = new int[32];
            for (int i = 0; i <= nums.length - 1; i++) {
                int n = nums[i];
                int idx = 0;
                while (n != 0) {
                    //System.out.println(n);
                    count[idx++] += (n & 1);
                    n = n >>> 1;
                }
            }
            int result = 0;
            for (int i = 0; i <= 31; i++) {
                if (count[i] % 3 != 0) {
                    result = result | (1 << i);
                }
            }
            return result == 0 ? -1 : result;
        }
    }

  • 0
    A

    Will this solution work for negative number?


  • 0
    J

    The python version:

    In python, we should notice that the range of int is [-2^63, 2^63-1].

    class Solution(object):
        def singleNumber(self, nums):
            cnt = [0] * 32
            for num in nums:
                i = 31
                while num and i >= 0:
                    cnt[i] += num & 1
                    num >>= 1
                    i -= 1
            result = 0
            for i in range(32):
                if cnt[i] % 3 == 1:
                    result += 1 << (31 - i)
            return result if result < (1 << 31) else result - (1 << 32)

  • 0
    A

    The above algorithm uses an intager to count the number of "1" on each bit of the intagers of the given array instead of some digital bits. Obviously, this one you provided is easy to understand, but I am afraid that the time complexity is higher than the requested, since in the original problem, linear time complexity is preffered.


  • 0
    P

    is this one a general solution for such kind of problems?


  • 0
    D

    @SummonYang How does that work?


  • 0
    L

    Thanks for sharing, your code is easy to understand:)


Log in to reply
 

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