Find the Number that Appears Odd Number of Times - Visualization

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

You are given an array of integers where exactly one number appears an odd number of times, and all other numbers appear an even number of times.

Your task is to find and return the number that occurs an odd number of times.

Use an efficient approach with bitwise operations, ideally O(n) time and O(1) space complexity.

Examples❯

Array Output Description
[1, 2, 3, 2, 3, 1, 3] 3 All numbers occur twice except 3, which occurs three times (odd)
[10] 10 Single element in array appears once (odd)
[5, 5, 7, 7, 9] 9 5 and 7 appear twice (even), 9 appears once (odd)
[0, 0, 1] 1 0 appears twice, 1 appears once (odd)
[100, 200, 100, 200, 300] 300 100 and 200 appear twice, 300 appears once (odd)
[] undefined Empty array; no number to process, behavior depends on implementation (e.g., return undefined or throw error)
[1, 1, 2, 2, 3, 3, 4, 4, 5] 5 Only 5 appears once (odd); others appear in pairs
[9, 9, 9] 9 9 appears three times (odd); valid input
[1, 2, 1, 2, 1] 1 1 appears three times (odd), 2 appears twice (even)
[42, 42, 42, 42, 42] 42 42 appears five times (odd), all values same

Solution❯

Understanding the Problem

We are given an array of integers where every number appears an even number of times, except for one number that appears an odd number of times.

Our goal is to identify this single number. We need to solve this efficiently in linear time O(n) and constant space O(1), which makes bitwise operations a good candidate.

For a beginner, this might sound tricky at first, but let’s break it down step by step using a smart bit manipulation trick: the XOR operation.

Step-by-Step Solution with Example

Step 1: Understand XOR Basics

The XOR (exclusive OR) operator, written as ^ in most languages, has a few important properties:

  • a ^ a = 0 – XORing a number with itself gives 0.
  • a ^ 0 = a – XORing a number with 0 gives the number itself.
  • XOR is associative and commutative – the order doesn't matter.

These properties mean that if we XOR all numbers in the array, the even-paired numbers cancel out and the only number left will be the one that appears an odd number of times.

Step 2: Initialize the Result Variable

Start with a variable result = 0. We will update it by XORing with every number in the array.

Step 3: Iterate and XOR

Let's go through an example:

arr = [1, 2, 3, 2, 3, 1, 3]

Here's how result changes step-by-step:


Initial result = 0
result = 0 ^ 1 = 1
result = 1 ^ 2 = 3
result = 3 ^ 3 = 0
result = 0 ^ 2 = 2
result = 2 ^ 3 = 1
result = 1 ^ 1 = 0
result = 0 ^ 3 = 3

At the end, result holds the value 3, which is the number that appears an odd number of times.

Step 4: Return the Result

Finally, return result as the answer.

Edge Cases

  • Array with only one element: If the array is like [7], the result is 7, since it appears once (odd).
  • Large numbers: The XOR method works regardless of how large the numbers are.
  • Negative numbers: The XOR operation works correctly even if the input contains negative integers.
  • Empty array: This would be an invalid input in our problem definition, as we expect exactly one odd-frequency number. We should handle or reject this input explicitly in real applications.

Final Thoughts

Using the XOR operation to find the number that appears an odd number of times is both elegant and efficient. It eliminates the need for extra space or complex logic.

This approach is powerful for problems involving even/odd pair behavior. As a beginner, understanding XOR through this example will help you tackle many more bit manipulation problems in the future!

Algorithm Steps❯

  1. Initialize a variable result with 0.
  2. Iterate over each number num in the array.
  3. For each number, perform result = result ^ num (XOR operation).
  4. At the end of the loop, result will hold the number that appears an odd number of times.
  5. This works because a ^ a = 0 and 0 ^ b = b.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int findOddOccurrence(int arr[], int size) {
    int result = 0;
    for (int i = 0; i < size; i++) {
        result ^= arr[i];
    }
    return result;
}

int main() {
    int arr[] = {2, 3, 2, 4, 4, 3, 5, 5, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    int odd = findOddOccurrence(arr, size);
    printf("Number appearing odd number of times: %d\n", odd);
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)Even in the best case, every element must be processed to apply the XOR operation. There’s no shortcut, as skipping any element could result in an incorrect result.
Average CaseO(n)The algorithm iterates through the array once, applying XOR on each element. Regardless of the data distribution, each element is processed once.
Worst CaseO(n)In the worst case, the array is large and all elements need to be traversed to compute the final XOR. This still results in a linear time complexity.

Space Complexity❯

O(1)

Explanation: The algorithm uses only a single variable to store the XOR result, regardless of the input size. No additional memory is allocated proportional to the input.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...