Master the problem of finding the number that appears odd number of times in an array with this beginner-friendly guide. Learn step-by-step how the XOR operation works to solve this problem efficiently in O(n) time and O(1) space. Includes detailed explanations, example walkthroughs, and fully working code in C, C++, Java, and Python. Perfect for coding interview preparation, competitive programming, and improving problem-solving skills.
In coding interviews and competitive programming, a popular problem is:
Find the Number That Appears Odd Number of Times
It’s a simple question, but there’s a clever trick to solve it efficiently. This article will explain the problem in depth, walk you through the logic step-by-step, and provide solutions in C, C++, Java, and Python.
Problem Statement
Given an array of integers, all numbers occur an even number of times except one. Your task is to find that number.
Example:
Input: arr = [2, 3, 2, 3, 4]
Output: 4
Explanation: 2 appears twice, 3 appears twice, and 4 appears once (odd number of times).
Naive Approach – Count Frequency
A beginner might think:
- Loop through the array.
- Count how many times each number occurs.
- Return the number with an odd count.
Problem:
- Time Complexity →
O(n²)(if we count for each number) - Not efficient for large datasets.
Naive Solution
int findOdd(int arr[], int n) {
// Outer loop: pick each element one by one
for (int i = 0; i < n; i++) {
int count = 0; // reset count for the current element
// Inner loop: compare the picked element with every element
for (int j = 0; j < n; j++) {
if (arr[i] == arr[j]) { // if both are same
count++; // increase occurrence count
}
}
// If the count is odd, return this number
if (count % 2 != 0) {
return arr[i];
}
}
return -1; // if no odd occurrence found
}How it works:
- Outer loop (
i) → Selects each number in the array one by one. - Inner loop (
j) → Compares that number with all elements in the array. count++→ Every time it matches, we increase the counter.- After the inner loop ends, we check:
if (count % 2 != 0)
If count is odd, that’s our answer.
Efficient Approach – Using XOR
The XOR ( ^ ) bitwise operator has special properties:
x ^ x = 0→ a number XORed with itself is 0.x ^ 0 = x→ a number XORed with 0 stays the same.- XOR is commutative and associative → order doesn’t matter.
Logic:
- If we XOR all elements in the array, numbers with even occurrences will cancel out to
0. - The result will be the number that occurs an odd number of times.
Example:
Array: [2, 3, 2, 3, 4]
Step 1: 2 ^ 3 = 1
Step 2: 1 ^ 2 = 3
Step 3: 3 ^ 3 = 0
Step 4: 0 ^ 4 = 4 ✅
Code Examples in Multiple Languages
1️⃣ C Program
#include
int findOdd(int arr[], int n) {
int result = 0;
for (int i = 0; i < n; i++) {
result ^= arr[i];
}
return result;
}
int main() {
int arr[] = {2, 3, 2, 3, 4};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Number appearing odd times: %d\n", findOdd(arr, n));
return 0;
}
2️⃣ C++ Program
#include
using namespace std;
int findOdd(int arr[], int n) {
int result = 0;
for (int i = 0; i < n; i++) {
result ^= arr[i];
}
return result;
}
int main() {
int arr[] = {2, 3, 2, 3, 4};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Number appearing odd times: " << findOdd(arr, n) << endl;
return 0;
}
3️⃣ Java Program
public class OddOccurrence {
static int findOdd(int[] arr) {
int result = 0;
for (int num : arr) {
result ^= num;
}
return result;
}
public static void main(String[] args) {
int[] arr = {2, 3, 2, 3, 4};
System.out.println("Number appearing odd times: " + findOdd(arr));
}
}
4️⃣ Python Program
def find_odd(arr):
result = 0
for num in arr:
result ^= num
return result
arr = [2, 3, 2, 3, 4]
print("Number appearing odd times:", find_odd(arr))
Key Takeaways
- XOR provides the most efficient solution.
- Time Complexity →
O(n) - Space Complexity →
O(1) - Works across all programming languages with the same logic.
- Very useful in interviews and competitive coding.
🔗 Read More Programming Tutorials: Embedded Prep Master
You can also Visit other tutorials of Embedded Prep
- Multithreading in C++
- Multithreading Interview Questions
- Multithreading in Operating System
- Multithreading in Java
- POSIX Threads pthread Beginner’s Guide in C/C++
- Speed Up Code using Multithreading
- Limitations of Multithreading
- Common Issues in Multithreading
- Multithreading Program with One Thread for Addition and One for Multiplication
- Advantage of Multithreading
- Disadvantages of Multithreading
- Applications of Multithreading: How Multithreading Makes Modern Software Faster and Smarter”
Mr. Raj Kumar is a highly experienced Technical Content Engineer with 7 years of dedicated expertise in the intricate field of embedded systems. At Embedded Prep, Raj is at the forefront of creating and curating high-quality technical content designed to educate and empower aspiring and seasoned professionals in the embedded domain.
Throughout his career, Raj has honed a unique skill set that bridges the gap between deep technical understanding and effective communication. His work encompasses a wide range of educational materials, including in-depth tutorials, practical guides, course modules, and insightful articles focused on embedded hardware and software solutions. He possesses a strong grasp of embedded architectures, microcontrollers, real-time operating systems (RTOS), firmware development, and various communication protocols relevant to the embedded industry.
Raj is adept at collaborating closely with subject matter experts, engineers, and instructional designers to ensure the accuracy, completeness, and pedagogical effectiveness of the content. His meticulous attention to detail and commitment to clarity are instrumental in transforming complex embedded concepts into easily digestible and engaging learning experiences. At Embedded Prep, he plays a crucial role in building a robust knowledge base that helps learners master the complexities of embedded technologies.
