Single Number

EASY

Description

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 * 10⁴
-3 * 10⁴ <= nums[i] <= 3 * 10⁴
Each element in the array appears twice except for one element which appears only once.

Approaches

Checkout 4 different approaches to solve Single Number. Click on different approaches to view the approach and algorithm in detail.

Brute Force Approach

This approach uses nested loops to find the single number. For each element in the array, we iterate through the entire array again to count its occurrences. If an element's count is one, it is the unique element.

Algorithm

1. Iterate through the array with an outer loop from i = 0 to n-1.
1. For each element nums[i], initialize a count variable to 0.
1. Start an inner loop from j = 0 to n-1.
1. Inside the inner loop, if nums[i] is equal to nums[j], increment count.
1. After the inner loop finishes, check if count is equal to 1.
1. If count is 1, nums[i] is the single number. Return nums[i].

The brute force method is the most straightforward way to solve the problem, but also the least efficient. The core idea is to check every element and see how many times it appears in the array.

We use two nested loops. The outer loop picks an element, and the inner loop iterates through the entire array to count the occurrences of the picked element. If the count for an element is exactly one, we have found our single number and can return it immediately.

public int singleNumber(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        int count = 0;
        for (int j = 0; j < nums.length; j++) {
            if (nums[i] == nums[j]) {
                count++;
            }
        }
        if (count == 1) {
            return nums[i];
        }
    }
    return -1; // Should not be reached given the problem constraints
}

Complexity Analysis

Time Complexity: O(n^2)Space Complexity: O(1)

Pros and Cons

Pros:

Simple to understand and implement.
Uses constant extra space.

Cons:

Highly inefficient with a quadratic time complexity.
Will likely result in a 'Time Limit Exceeded' error for large inputs.

Code Solutions

Checking out 5 solutions in different languages for Single Number. Click on different languages to view the code.

public class Solution {
    public int SingleNumber(int[] nums) {
        return nums.Aggregate(0, (a, b) => a ^ b);
    }
}

Video Solution

Watch the video walkthrough for Single Number

Patterns:

Bit Manipulation

Data Structures:

Array

Companies:

Airbnb |Cisco |Google |Nvidia |