Lonely Integer

Given an array of integers where each number appears a certain number of times except for one unique number, find the number that appears an odd number of times. You must do this efficiently.

bit manipulationXORarraylinear timeconstant space

Problem Statement

You are given a non-empty array of integers. Every number in the array appears an even number of times except for one number which appears an odd number of times. Your task is to find that single number that occurs an odd number of times. For example, in the array [7, 3, 5, 4, 5, 3, 4], the number 7 appears only once, so you should return 7.

Example 1

Input: [2, 2, 1]

Output: 1

The number 2 appears twice, while the number 1 appears only once. Therefore, the number that appears an odd number of times is 1.

Example 2

Input: [7, 3, 5, 4, 5, 3, 4]

Output: 7

The numbers 3, 4, and 5 each appear twice, while the number 7 appears only once. Therefore, the number that appears an odd number of times is 7.

Constraints

-The array will contain at least one integer.
-There will be exactly one integer that appears an odd number of times.
-The integers in the array can be positive, negative, or zero.
-The array can contain up to 100000 integers.

Brute Force Approach

A brute force approach would involve iterating through the array and, for each number, iterating through the rest of the array to count how many times it appears. This is like manually checking each item in a large pile to see how many duplicates it has before moving on to the next item.

TimeO(n^2)

SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem