Find the Number Appearing Once in Python

Finding a unique number in a list that appears only once while all other numbers appear twice is a common and important problem in programming. We can find the unique number in a list using multiple ways.

The most efficient approach is using an XOR operator, as this method solves this problem in constant time and space complexity. In this article, we are going to discuss various approaches to finding the number that appears once while all others appear twice.

Finding the Unique Number

When we are given a list of numbers where every number appears twice except one number, we have to find the number that appears only once.

Input & Output Scenarios

Example1

Input:
[4, 3, 2, 4, 3]
Output:
2

Explanation

The number 4 appears twice, the number 3 appears twice, but the number 2 appears only once.

Example 2

Input:
[1, 1, 2, 2, 3]
Output:
3

Explanation

The number 1 appears twice, the number 2 appears twice, but the number 3 appears only once.

Using the XOR Operator Approach

This is the most efficient approach for finding the unique number. This XOR operator ( ^ ) helps in eliminating duplicate numbers since we know that for any number N: N ^ N = 0, and 0 ^ N = N.

Steps for Implementation

• Initialize a variable unique_number to 0.
• Iterate through the list and perform the XOR with each number.
• The result will be a unique number that occurs only once.

Example

nums = [4, 3, 2, 4, 3]
unique_number = 0
for num in nums:
    unique_number ^= num
print(f"The number that appears once is: {unique_number}")

Output

The number that appears once is: 2

Time Complexity : O(N)

Using Dictionary (Hash Map) Approach

In this approach, we use a dictionary to store the frequency of each number. The number that appears once will have a frequency of 1 and all other numbers have a frequency of 2.

Steps for Implementation

• Initialize an empty dictionary.
• Traverse through the list and count occurrences of each number.
• Find the number with a frequency of 1.

Example

nums = [1, 1, 2, 2, 3]
frequency = {}
for num in nums:
    frequency[num] = frequency.get(num, 0) + 1
for num, count in frequency.items():
    if count == 1:
        print(f"The number that appears once is: {num}")
        break

Output

The number that appears once is: 3

Time Complexity : O(N)

Using List Count Method

This is a simple approach where we use Python's count() method to check how many times each number appears in the list.

Steps for Implementation

• Iterate through the list.
• Use count() to check the frequency of each number.
• Return the number with a frequency of 1.

Example

nums = [4, 3, 2, 4, 3]
for num in nums:
    if nums.count(num) == 1:
        print(f"The number that appears once is: {num}")
        break

Output

The number that appears once is: 2

Time Complexity : O(N^2)

Using Set Difference Approach

In this approach, we use a set to find the unique number that appears once in a given list. A Set is a data structure that stores only unique elements.

Steps for Implementation

• First, convert the list into a set to remove duplicates and sum the elements of the set.
• Multiply the sum by 2 (since duplicate elements are removed from the set) and
• Subtract the sum of the original list.
• The result is a unique number of list since all the duplicate elements get canceled out.

Example

nums = [1, 1, 2, 2, 3]
unique = 2 * sum(set(nums)) - sum(nums)
print(f"The number that appears once is: {unique}")

Output

The number that appears once is: 3

Time Complexity : O(N)

Using a Loop (Checking Every Element)

This is a very simple brute-force approach to find the number that occurs once. In this approach, we compare each number with every number in the list.

Steps for Implementation

• Iterate through the list.
• Compare each number with every other number in the list.
• If a number appears only once in the entire list, print and return it.

Example

nums = [4, 3, 2, 4, 3]
for i in range(len(nums)):
    found = False
    for j in range(len(nums)):
        if i != j and nums[i] == nums[j]:
            found = True
            break
    if not found:
        print(f"The number that appears once is: {nums[i]}")
        break

Output

The number that appears once is: 2

Time Complexity : O(N^2)