Single Number

Easyarraybit-manipulation

Category: Bit Manipulation

Companies that ask this question:

AmazonGoogleFacebookMicrosoftApple

Approach

Single Number

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 O(n) time complexity and O(1) space complexity.

Examples

Example 1:

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

Example 2:

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

Approach

Use XOR bit manipulation. XOR properties:

a ⊕ a = 0
a ⊕ 0 = a
Commutative: a ⊕ b = b ⊕ a

All pairs cancel out, leaving the single number.

Complexity

Time: O(n)
Space: O(1)

Solution

java

1class Solution {
2    public int singleNumber(int[] nums) {
3        int result = 0;
4        for (int num : nums) {
5            result ^= num;
6        }
7        return result;
8    }
9}

Loading visualizer...