Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/136.html

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

 

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

 

Constraints:

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• Each element in the array appears twice except for one element which appears only once.

Algorithm

Using a HashSet

A direct idea is to use a HashSet due to its constant search speed. Traverse each number in the array, and if the current number is already in the HashSet, remove the number from the HashSet; otherwise, add it to the HashSet.

This is equivalent to offsetting two by two. In the end, all the numbers that appear twice are removed from the HashSet, and the only number left is the single number.

Using Bitwise Operations

Since numbers are stored in binary in computers, each bit is either 0 or 1. If we XOR two identical numbers, the exclusive OR of 0 and 0 is 0, and the exclusive OR of 1 and 1 is also 0.

Therefore, if we XOR all the numbers in the array, each pair of identical numbers will result in 0, and the only number that appears once will be left.

Here are two important points to consider:

1. num^num = 0
2. Carefully initialize the sum to 0. Use a simple test case to confirm this.

Code

• Java
• C++
• Python
• Go
• TypeScript
• Javascript
• RenderScript
• Swift

• 
  public class Single_Number {
  
      public class Solution {
          public int singleNumber(int[] nums) {
  
              if (nums == null || nums.length == 0) {
                  return -1;
              }
  
              int a = nums[0];
              for (int i = 1; i < nums.length; i++) {
                  a ^= nums[i];
              }
  
              return a;
          }
      }
  }
  
  ############
  
  class Solution {
      public int singleNumber(int[] nums) {
          int ans = 0;
          for (int v : nums) {
              ans ^= v;
          }
          return ans;
      }
  }
  

• // OJ: https://leetcode.com/problems/single-number/
  // Time: O(N)
  // Space: O(1)
  class Solution {
  public:
      int singleNumber(vector<int>& nums) {
          int ans = 0;
          for (int n : nums) ans ^= n;
          return ans;
      }
  };
  

• '''
  >>> from functools import reduce
  >>> reduce(lambda x, y: x ^ y, [3, 5, 3])
  5
  '''
  class Solution:
      def singleNumber(self, nums: List[int]) -> int:
          return reduce(lambda x, y: x ^ y, nums)
  
  ############
  
  class Solution(object):
    def singleNumber(self, nums):
      """
      :type nums: List[int]
      :rtype: int
      """
      for i in range(1, len(nums)):
        nums[0] ^= nums[i]
      return nums[0]
  
  

• func singleNumber(nums []int) (ans int) {
  	for _, v := range nums {
  		ans ^= v
  	}
  	return
  }
  

• function singleNumber(nums: number[]): number {
      return nums.reduce((r, v) => r ^ v);
  }
  
  

• /**
   * @param {number[]} nums
   * @return {number}
   */
  var singleNumber = function (nums) {
      let ans = 0;
      for (const v of nums) {
          ans ^= v;
      }
      return ans;
  };
  
  

• impl Solution {
      pub fn single_number(nums: Vec<i32>) -> i32 {
          nums.into_iter().reduce(|r, v| r ^ v).unwrap()
      }
  }
  
  

• class Solution {
      func singleNumber(_ nums: [Int]) -> Int {
          var a = nums.sorted()
          var n = a.count
          for i in stride(from: 0, through: n - 2, by: 2) {
              if a[i] != a[i + 1] {
                  return a[i]
              }
          }
          return a[n - 1]
      }
  }
  

All Problems

All Solutions