Find the Number that Appears Odd Number of Times

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.

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!

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.

#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;
}

#include <iostream>
#include <vector>
using namespace std;

int findOddOccurrence(const vector<int>& arr) {
    int result = 0;
    for (int num : arr) {
        result ^= num;
    }
    return result;
}

int main() {
    vector<int> arr = {2, 3, 2, 4, 4, 3, 5, 5, 5};
    cout << "Number appearing odd number of times: " << findOddOccurrence(arr) << endl;
    return 0;
}

def find_odd_occurrence(arr):
    result = 0
    for num in arr:
        result ^= num
    return result

arr = [2, 3, 2, 4, 4, 3, 5, 5, 5]
print("Number appearing odd number of times:", find_odd_occurrence(arr))

public class OddOccurrence {
    public static int findOddOccurrence(int[] arr) {
        int result = 0;
        for (int num : arr) {
            result ^= num;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 2, 4, 4, 3, 5, 5, 5};
        System.out.println("Number appearing odd number of times: " + findOddOccurrence(arr));
    }
}

function findOddOccurrence(arr) {
  let result = 0;
  for (const num of arr) {
    result ^= num;
  }
  return result;
}

const arr = [2, 3, 2, 4, 4, 3, 5, 5, 5];
console.log("Number appearing odd number of times:", findOddOccurrence(arr));

package main

import "fmt"

func findOddOccurrence(arr []int) int {
    result := 0
    for _, num := range arr {
        result ^= num
    }
    return result
}

func main() {
    arr := []int{2, 3, 2, 4, 4, 3, 5, 5, 5}
    fmt.Printf("Number appearing odd number of times: %d\n", findOddOccurrence(arr))
}

fn find_odd_occurrence(arr: &[i32]) -> i32 {
    arr.iter().fold(0, |acc, &x| acc ^ x)
}

fn main() {
    let arr = [2, 3, 2, 4, 4, 3, 5, 5, 5];
    println!("Number appearing odd number of times: {}", find_odd_occurrence(&arr));
}

fun findOddOccurrence(arr: IntArray): Int {
    var result = 0
    for (num in arr) {
        result = result xor num
    }
    return result
}

fun main() {
    val arr = intArrayOf(2, 3, 2, 4, 4, 3, 5, 5, 5)
    println("Number appearing odd number of times: ${findOddOccurrence(arr)}")
}

func findOddOccurrence(_ arr: [Int]) -> Int {
    var result = 0
    for num in arr {
        result ^= num
    }
    return result
}

let arr = [2, 3, 2, 4, 4, 3, 5, 5, 5]
print("Number appearing odd number of times: \(findOddOccurrence(arr))")

function findOddOccurrence(arr: number[]): number {
  let result = 0;
  for (const num of arr) {
    result ^= num;
  }
  return result;
}

const arr = [2, 3, 2, 4, 4, 3, 5, 5, 5];
console.log("Number appearing odd number of times:", findOddOccurrence(arr));

Time complexity

Space complexity

O(1)

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.