Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Single Number
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

In a non-empty array of integers, every number appears twice except for one, find that single number.

Example 1:

Input: 1, 4, 2, 1, 3, 2, 3
Output: 4

Example 2:

Input: 7, 9, 7
Output: 9

Constraints:

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

Solution

One straight forward solution can be to use a HashMap kind of data structure and iterate through the input:

  1. If number is already present in HashMap, remove it.
  2. If number is not present in HashMap, add it.
  3. In the end, only number left in the HashMap is our required single number.

Time and space complexity Time Complexity of the above solution will be O(n) and space complexity will also be O(n).

Can we do better than this using the XOR Pattern?

Solution with XOR

Recall the following two properties of XOR:

  1. It returns zero if we take XOR of two same numbers.
  2. It returns the same number if we XOR with zero.

So we can XOR all the numbers in the input; duplicate numbers will zero out each other and we will be left with the single number.

Code

Here is what our algorithm will look like:

Python3
Python3
. . . .

Time Complexity

Time complexity of this solution is O(n) as we iterate through all numbers of the input once.

Space Complexity

The algorithm runs in constant space O(1).

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible