Leetcode. Single Number I, II, III

Single Number I

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Python (v1)
Time complexity: O(N)
Space complexity: O(1)


class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        xor = 0
        for n in nums:
            xor ^= n
        return xor

Python (v2)
Time complexity: O(N)
Space complexity: O(1)


from functools import reduce
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        xor = reduce((lambda x, y: x ^ y), nums)
        return xor

 

Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Java (extra memory)
Time complexity: O(N)
Space complexity: O(1)

public class Solution {
    public int singleNumber(int[] A) {
        // write your code here
        if (A.length == 1){
            return A[0];
        }
        
        int[] bitCount = new int[32];
        for (int a : A){
            for (int i = 0; i < 32; ++i){
                boolean isSet = (a & (1 << i)) != 0; if (isSet){ bitCount[i] = (bitCount[i] + 1) % 3; } } } int res = 0; for (int i = 31; i >= 0; --i){
            res |= bitCount[i] << i;    
        }
        
        return res;
            
    }
}

Java
Time complexity: O(N)
Space complexity: O(1)

public class Solution {
    public int singleNumber(int[] A) {
        // write your code here
        int ones = 0;
        int twos = 0;
        for (int i = 0; i < nums.length; ++i){
            ones = (ones ^ nums[i]) & ~twos;
            twos = (twos ^ nums[i]) & ~ones;
        }
        return ones;            
    }
}

Java (extended to 4 times case)
Time complexity: O(N)
Space complexity: O(1)

public class Solution {
    public int singleNumber(int[] A) {
        int ones = 0;
        int twos = 0;

        for (int i = 0; i < nums.length; ++i){
            ones = (ones ^ nums[i]) & ~(twos & ones);
            twos = (twos ^ nums[i]) & ~ones & ~(twos & ones);
        }
        return ones;           
    }
}

 

Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

  1. The order of the result is not important. So in the above example, [5, 3] is also correct.
  2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Java
Time complexity: O(N)
Space complexity: O(1)

public class Solution {
    public int[] singleNumber(int[] nums) {
        // write your code here
        int[] res = new int[2];
        
        if (nums == null || nums.length == 0){
            return res;
        }
        
        int diff = 0;
        
        for (int n : nums){
            diff ^= n;
        }
        
        diff &= ~(diff - 1);
        
        for (int n : nums){
            if ((n & diff) != 0){
                res[0] ^= n;
            } else {
                res[1] ^= n;    
            } 
        }
        
        return res;
           
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s