136. Single Number
Single Number (LeetCode 136) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Bit Manipulation Patterns pattern, in the Bitwise XOR - Finding Single/Missing Number subpattern.
How to solve Single Number
Single Number is a XOR for Single and Missing Numbers problem, part of Bit Manipulation Patterns. Use XOR properties to find single number, missing number, and duplicates.
Work towards the solution in these steps:
- Think about the XOR (^) operator's property.
The reference solution runs in O(n) time and O(1) space.
The Single Number solution and editorial walks through the full approach with reference code.
Problem statement
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.
Topics and companies
Topics: Array, Bit Manipulation.
Reported in interviews at Google, Amazon, Facebook, Microsoft.
How to practise Single Number on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Single Number in the code editor, or read the Single Number editorial for a worked solution with its approach and complexity analysis.
Where Single Number sits in the DSA pattern sheet
- Bit Manipulation Patterns pattern guide
- Bitwise XOR - Finding Single/Missing Number subpattern
- The full DSA patterns sheet
Problems related to Single Number
Other problems that use the same Bitwise XOR - Finding Single/Missing Number and Bit Manipulation Patterns techniques:
- Find the Difference — Easy, same subpattern
- Missing Number — Easy, same subpattern
- Single Number II — Medium, same subpattern
- Sum of Two Integers — Medium, same subpattern
- Bitwise AND of Numbers Range — Medium, same pattern
- Counting Bits — Easy, same pattern
Single Number FAQ
What is the LeetCode number of Single Number?
Single Number is LeetCode problem 136, rated Easy.
What pattern is used to solve Single Number?
Single Number is a XOR for Single and Missing Numbers problem. It belongs to the Bit Manipulation Patterns pattern, in the Bitwise XOR - Finding Single/Missing Number subpattern.
What is the time complexity of Single Number?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Single Number?
Single Number has been reported in interviews at Google, Amazon, Facebook, Microsoft.