137. Single Number II
Single Number II (LeetCode 137) is a Medium 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 II
Single Number II 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:
- Consider how bit manipulation can help identify unique elements when others appear multiple times.
- Think about counting the number of times each bit is set across all numbers and how that relates to the repetition count.
- Try using an array or fixed-size structure to count bits at each position, then analyze these counts modulo three.
The reference solution runs in O(n) time and O(1) space.
The Single Number II solution and editorial walks through the full approach with reference code.
Problem statement
Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Example 1:
Input: nums = [2,2,3,2] Output: 3
Example 2:
Input: nums = [0,1,0,1,0,1,99] Output: 99
Constraints:
- 1 <= nums.length <= 3 104
- -231 <= nums[i] <= 231 - 1
- Each element in nums appears exactly three times except for one element which appears once.
Topics and companies
Topics: Array, Bit Manipulation.
Reported in interviews at Google, Adobe.
How to practise Single Number II 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 II in the code editor, or read the Single Number II editorial for a worked solution with its approach and complexity analysis.
Where Single Number II 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 II
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 — Easy, same subpattern
- Sum of Two Integers — Medium, same subpattern
- Bitwise AND of Numbers Range — Medium, same pattern
- Counting Bits — Easy, same pattern
Single Number II FAQ
What is the LeetCode number of Single Number II?
Single Number II is LeetCode problem 137, rated Medium.
What pattern is used to solve Single Number II?
Single Number II 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 II?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Single Number II?
Single Number II has been reported in interviews at Google, Adobe.