Teaching Kids Programming – Find the Single Number in Array

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?

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
 
Each element in the array appears twice except for one element which appears only once.

Bruteforce Algorithm to Find the Single Number

We go through each possible pair and check if two are the same. Time complexity O(N^2) quadratic and space complexity is O(1) constant.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            flag = True
            for j in range(n):
                if j != i and nums[i] == nums[j]:
                    flag = False
                    break
            if flag:
                return nums[i]

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            flag = True
            for j in range(n):
                if j != i and nums[i] == nums[j]:
                    flag = False
                    break
            if flag:
                return nums[i]

Using Hash Table to Find the Single Number

We can count the appearance of each number using the Counter object, and then go through the keys of the dictionary, and return it if it has value 1 (appearing only once):

1
2
3
4
5
6

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        x = Counter(nums)
        for a in x.keys():
            if x[a] == 1:
                return a

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        x = Counter(nums)
        for a in x.keys():
            if x[a] == 1:
                return a

Time complexity is O(N), and space complexity is O(N).

Using XOR (Exclusive OR) to Find the Single Number

The XOR of two same numbers is zero. Thus we can perform the XOR on all the numbers in the array, the result will be the single number that is left out.

1
2
3
4
5
6

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        x = 0
        for i in nums:
            x ^= i
        return

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        x = 0
        for i in nums:
            x ^= i
        return

Time complexity is O(N) as we are iterating once the numbers in the array. The space complexity is O(1) constant.

We can use the reduce function:

1
2
3
4
5

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        def f(a, b):
            return a ^ b
        return reduce(f, nums, 0)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        def f(a, b):
            return a ^ b
        return reduce(f, nums, 0)

Or even better, using the lambda function:

1
2
3

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda a, b: a^b, nums, 0)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda a, b: a^b, nums, 0)

See also: Coding Exercise – C++ – Single Number – Online Judge

–EOF (The Ultimate Computing & Technology Blog) —