General solution - Constant Space


  • 10
    N
    class Solution {   
    public:
    int singleNumber(int A[], int n) {
        int sum = 0;
    	int result = 0;
    	int x = 0;
        int mod = 3;
        for(int i = 0; i < 32 ; i++){
    		sum = 0;
            x = (1 << i);
            for(int j = 0; j < n; j++){
            	if((A[j] & x)){
            		sum++;
            	}
            }
            if((sum % mod)){
            	result |= x;
            }
        }
        return result;
      }
    };
    

    We can sum the bits in same positions for all the numbers and take modulo 3. The bits for which sum is not multiple of 3, are the bits of number which does not occur 3 times.

    Example array {5, 5, 5, 8}.

    5 = 0101, 5 = 0101, 5 = 0101, 8 = 1000

    Sum of first bits%3 = (1 + 1 + 1 + 0)%3 = 0;

    Sum of second bits%3 = (0 + 0 + 0 + 0)%3 = 0;

    Sum of third bits%3 = (1 + 1 + 1 + 0)%3 = 0;

    Sum of fourth bits%3 = (1)%3 = 1;

    Hence number which appears once is 1000
    We can use that method for any number of occurrences. We just need to modify the mod from 3 to anything we want.


  • 0
    X

    Thanks for the answer. Although this is not the optimal one (it takes O(32n) complexity because of the outer loop), but it is easy to understand and it is more likely to be the solution that one can quickly come up during an interview.


Log in to reply
 

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