Bit manipulation: find a bit in which both nums are different: same technique can be used with other similar questions.


  • 0
    class Solution {
    public:
        vector<int> singleNumber(vector<int>& nums) {
            vector<int> result;
            int size = nums.size();
            
            int c = 0;
            for(int i = 0;i < size; i++){
                c = c ^ nums[i];
            }
    
            int mask = c - (c&(c-1)); //(or do c & (-c)
            int lh = 0, rh = 0;
            for(int i = 0; i < size; i++){
                if(nums[i]&mask){
                    lh = lh ^ nums[i];
                }else{
                    rh = rh ^ nums[i];
                }
            }
            result = {lh, rh};
            return result;
        }
    };

  • 1

    To this about this: you can use the same technique of looking at individual bits. For example, assume you want to find one number that is repeated only once as compare to every other number that is repeated twice: besides the typical xoring approach, you can count the number of 1s set in every ith position, and take that module 2 (since each number exists twice), if the answer is 1, means the number you're looking for is 1, other wise its zero. That way you can construct all bits of the missing number. This can be generalized over here as well.


  • 1
    D
    public class Solution {
        public int[] singleNumber(int[] a) {
            int x =a.length;
          
            HashSet<Integer> s = new HashSet<Integer>();
            for(int i = 0 ; i < x;i++)
            {
                if(!(s.contains(a[i])))
                {
                    s.add(a[i]);
                    
                    //b[i]=a[i];
                }
                else
                {
                    s.remove(a[i]);
                }
            }
              int b[] = new int[s.size()];
              
              int h =0;
             for(Integer val:s)
             {
                 b[h++]=val;
             }
             return b;
        }
    }

Log in to reply
 

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