Method 1: Brute Force
One way to find the number with odd frequency is to linearly pick every number and count its number of occurrences in the array.
Refer to the algorithm given below.
Algorithm
- Loop ‘i’ from 0 to ‘SIZE’ (size of the array)
- Set COUNTER = 0 (frequency of each element)
- Loop ‘j’ from 0 to ‘SIZE’
- If ‘ARR[i]’ equals to ‘ARR[j]’
- Increment ‘COUNTER’
- If ‘COUNTER’ is not divisible by 2
- If no number is returned in the loop
Code
C++
#include <iostream>
#include <vector>
using namespace std;
// Function to check whether a number is a power of two.
int findOddOccurrence(vector<int> &arr)
{
int size = arr.size();
// Loop to traverse the array.
for (int i = 0; i < size; i++)
{
// The 'COUNTER' variable will count the occurrence of element 'ARR[i]'.
int counter = 0;
for (int j = 0; j < size; j++)
{
// If an element is found, increment the 'COUNTER'.
if (arr[i] == arr[j])
{
counter++;
}
}
// If the element has an odd occurrence, return the element.
if (counter % 2 == 1)
{
return arr[i];
}
}
// If no element with odd occurrence is found, return -1.
return -1;
}
int main()
{
// Taking user input.
cout << "Enter the size of the array: ";
int n;
cin >> n;
vector<int> arr(n);
cout << "Enter " << n << " elements: ";
for (int &i : arr)
{
cin >> i;
}
// Calling findOddOccurrence() function.
cout << "The element with odd frequency is: " << findOddOccurrence(arr);
return 0;
}
You can also try this code with Online C++ Compiler
Java
import java.util.Scanner;
public class OddOccurrence {
public static int findOddOccurrence(int[] arr) {
int size = arr.length;
for (int i = 0; i < size; i++) {
int counter = 0;
for (int j = 0; j < size; j++) {
if (arr[i] == arr[j]) {
counter++;
}
}
if (counter % 2 == 1) {
return arr[i];
}
}
return -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter the size of the array: ");
int n = sc.nextInt();
int[] arr = new int[n];
System.out.println("Enter " + n + " elements:");
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
System.out.println("The element with odd frequency is: " + findOddOccurrence(arr));
}
}
You can also try this code with Online Java Compiler
Python
def find_odd_occurrence(arr):
size = len(arr)
for i in range(size):
counter = 0
for j in range(size):
if arr[i] == arr[j]:
counter += 1
if counter % 2 == 1:
return arr[i]
return -1
# Taking input
n = int(input("Enter the size of the array: "))
arr = list(map(int, input(f"Enter {n} elements: ").split()))
print("The element with odd frequency is:", find_odd_occurrence(arr))
You can also try this code with Online Python Compiler
JS
function findOddOccurrence(arr) {
const size = arr.length;
for (let i = 0; i < size; i++) {
let counter = 0;
for (let j = 0; j < size; j++) {
if (arr[i] === arr[j]) {
counter++;
}
}
if (counter % 2 === 1) {
return arr[i];
}
}
return -1;
}
// Example input
const readline = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});
readline.question("Enter the size of the array: ", size => {
readline.question(`Enter ${size} elements: `, elements => {
const arr = elements.trim().split(" ").map(Number);
console.log("The element with odd frequency is:", findOddOccurrence(arr));
readline.close();
});
});
You can also try this code with Online Javascript Compiler
PHP
<?php
function findOddOccurrence($arr) {
$size = count($arr);
for ($i = 0; $i < $size; $i++) {
$counter = 0;
for ($j = 0; $j < $size; $j++) {
if ($arr[$i] == $arr[$j]) {
$counter++;
}
}
if ($counter % 2 == 1) {
return $arr[$i];
}
}
return -1;
}
// Input
echo "Enter the size of the array: ";
$size = (int)trim(fgets(STDIN));
echo "Enter $size elements separated by space: ";
$arr = explode(" ", trim(fgets(STDIN)));
$arr = array_map('intval', $arr);
echo "The element with odd frequency is: " . findOddOccurrence($arr) . PHP_EOL;
?>
You can also try this code with Online PHP Compiler
Complexity Analysis
Time complexity: The code uses two nested for loops. The first for loop is used to traverse every element of the array, ‘ARR’. And, for every element, we use a second for loop to compute the frequency, which takes O(N) time. So, the overall time complexity is O(N * N) = O(N2).
Space Complexity: The code does not require any extra space to run. So, the space required is independent of the size of the input given. Space complexity is O(1).
Also see, Morris Traversal for Inorder and Rabin Karp Algorithm
Method 2: Hashmaps
Hashmap works in O(1) time complexity for insertion and lookup. So, it can be an easy alternative to the brute force method. Store the frequency corresponding to each element in a hashmap. Return the element which has an odd frequency.
Refer to the algorithm given below for this method.
Algorithm
- Create a hashmap ‘MP’.
- Iterate through ‘ARR’ using the iterator ‘IT’.
- If ‘IT’ does not exist as a key in the hashmap
- Insert ‘IT’ in the hashmap
- Increment the value of ‘MP[IT]’
- Iterate through the hashmap ‘MP’.
- If the iterator value is odd
- Return -1
Code
C++
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
// Function to check whether a number is a power of two.
int findOddOccurrence(vector<int> &arr)
{
int size = arr.size();
unordered_map<int, int> mp;
// Iteration to store the keys and corresponding frequencies in hashmap.
for (int &it : arr)
{
mp[it]++;
}
// Iterating on hashmap to find which of the keys has an odd frequency.
for (auto it : mp)
{
// If the value of the iterator is odd, return the key.
if (it.second % 2 != 0)
{
return it.first;
}
}
// If no element with odd occurrence is found, return -1.
return -1;
}
int main()
{
// Taking user input.
cout << "Enter the size of the array: ";
int n;
cin >> n;
vector<int> arr(n);
cout << "Enter " << n << " elements: ";
for (int &i : arr) {
cin >> i;
}
// Calling findOddOccurrence() function.
cout << "The element with odd frequency is: " << findOddOccurrence(arr);
return 0;
}
You can also try this code with Online C++ Compiler
Java
import java.util.HashMap;
import java.util.Scanner;
public class OddOccurrence {
public static int findOddOccurrence(int[] arr) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : arr) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
for (int key : map.keySet()) {
if (map.get(key) % 2 != 0) {
return key;
}
}
return -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter the size of the array: ");
int n = sc.nextInt();
int[] arr = new int[n];
System.out.println("Enter " + n + " elements:");
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
System.out.println("The element with odd frequency is: " + findOddOccurrence(arr));
}
}
You can also try this code with Online Java Compiler
Python
def find_odd_occurrence(arr):
freq = {}
for num in arr:
freq[num] = freq.get(num, 0) + 1
for key, value in freq.items():
if value % 2 != 0:
return key
return -1
# Input from user
n = int(input("Enter the size of the array: "))
arr = list(map(int, input(f"Enter {n} elements: ").split()))
print("The element with odd frequency is:", find_odd_occurrence(arr))
You can also try this code with Online Python Compiler
JS
function findOddOccurrence(arr) {
const freqMap = new Map();
for (let num of arr) {
freqMap.set(num, (freqMap.get(num) || 0) + 1);
}
for (let [key, value] of freqMap.entries()) {
if (value % 2 !== 0) {
return key;
}
}
return -1;
}
// Input Handling
const readline = require("readline").createInterface({
input: process.stdin,
output: process.stdout
});
readline.question("Enter the size of the array: ", size => {
readline.question(`Enter ${size} elements: `, elements => {
const arr = elements.trim().split(" ").map(Number);
console.log("The element with odd frequency is:", findOddOccurrence(arr));
readline.close();
});
});
You can also try this code with Online Javascript Compiler
PHP
<?php
function findOddOccurrence($arr) {
$freq = [];
foreach ($arr as $num) {
if (isset($freq[$num])) {
$freq[$num]++;
} else {
$freq[$num] = 1;
}
}
foreach ($freq as $key => $value) {
if ($value % 2 != 0) {
return $key;
}
}
return -1;
}
// Input
echo "Enter the size of the array: ";
$size = (int)trim(fgets(STDIN));
echo "Enter $size elements separated by space: ";
$arr = explode(" ", trim(fgets(STDIN)));
$arr = array_map('intval', $arr);
echo "The element with odd frequency is: " . findOddOccurrence($arr) . PHP_EOL;
?>
You can also try this code with Online PHP Compiler
Complexity Analysis
Time complexity: The code uses two independent for loops. So, the time complexity is O(N + N) = O(N).
Space Complexity: As the size of the hashmap depends linearly on the size of the array, the space complexity of the method is O(N).
Method 3: Bit Manipulation
Do you remember XOR operations? Don’t worry if you don’t. Here’s a quick revision for the same. Refer to the truth table given below for XOR operations.
Consider XOR of all elements of the array stored as ‘X’. Elements present in even numbers will not affect the bits of ‘X’. One occurrence unsets the bits set by the other one.
Refer to the image given below for a better understanding.
Neat trick, isn’t it? Refer to the algorithm given below to understand the implementation procedure.
Algorithm
- Set ANSWER = 0
- Loop ‘i‘ from 0 to ‘SIZE’ (size of the array)
- Set ANSWER = ANSWER ^ ARR[I]
- If ANSWER = 0, return -1 else return ‘ANSWER’
Code
C++
#include <iostream>
#include <vector>
using namespace std;
// Function to check whether a number is a power of two.
int findOddOccurrence(vector<int> &arr)
{
int size = arr.size();
int answer = 0;
// Loop to iterate through the list.
for (int i = 0; i < size; i++)
{
// Doing bitwise XOR of current element with answer.
answer = answer ^ arr[i];
}
return (answer == 0) ? -1 : answer;
}
int main()
{
// Taking user input.
cout << "Enter the size of the array: ";
int n;
cin >> n;
vector<int> arr(n);
cout << "Enter " << n << " elements: ";
for (int &i : arr)
{
cin >> i;
}
// Calling findOddOccurrence() function.
cout << "The element with odd frequency is: " << findOddOccurrence(arr);
return 0;
}
You can also try this code with Online C++ Compiler
Java
import java.util.Scanner;
public class OddOccurrence {
public static int findOddOccurrence(int[] arr) {
int answer = 0;
for (int num : arr) {
answer ^= num; // XOR operation
}
return (answer == 0) ? -1 : answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter the size of the array: ");
int n = sc.nextInt();
int[] arr = new int[n];
System.out.println("Enter " + n + " elements:");
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
System.out.println("The element with odd frequency is: " + findOddOccurrence(arr));
}
}
You can also try this code with Online Java Compiler
Python
def find_odd_occurrence(arr):
answer = 0
for num in arr:
answer ^= num # XOR operation
return -1 if answer == 0 else answer
# Input from user
n = int(input("Enter the size of the array: "))
arr = list(map(int, input(f"Enter {n} elements: ").split()))
print("The element with odd frequency is:", find_odd_occurrence(arr))
You can also try this code with Online Python Compiler
JS
function findOddOccurrence(arr) {
let answer = 0;
for (let num of arr) {
answer ^= num; // XOR operation
}
return answer === 0 ? -1 : answer;
}
// Input Handling
const readline = require("readline").createInterface({
input: process.stdin,
output: process.stdout
});
readline.question("Enter the size of the array: ", size => {
readline.question(`Enter ${size} elements: `, elements => {
const arr = elements.trim().split(" ").map(Number);
console.log("The element with odd frequency is:", findOddOccurrence(arr));
readline.close();
});
});
You can also try this code with Online Javascript Compiler
PHP
<?php
function findOddOccurrence($arr) {
$answer = 0;
foreach ($arr as $num) {
$answer ^= $num; // XOR operation
}
return ($answer == 0) ? -1 : $answer;
}
// Input
echo "Enter the size of the array: ";
$n = (int)trim(fgets(STDIN));
echo "Enter $n elements separated by space: ";
$arr = explode(" ", trim(fgets(STDIN)));
$arr = array_map('intval', $arr);
echo "The element with odd frequency is: " . findOddOccurrence($arr) . PHP_EOL;
?>
You can also try this code with Online PHP Compiler
Complexity Analysis
Time complexity: The code uses a linear loop. So, the time complexity is O(N).
Space Complexity: Constant space is used. So, the space complexity is O(1)
Frequently Asked Questions
What does it mean when a number occurs an odd number of times?
It means the number appears in the array or list an odd number of times, such as 1, 3, 5, etc. All other numbers typically appear an even number of times.
What is the most efficient way to find the number occurring odd times?
Using the XOR (^) operator is the most efficient way. XORing all elements in the array returns the number that occurs an odd number of times in linear time and constant space.
Can there be more than one number occurring an odd number of times?
Yes, in some variations of the problem, multiple numbers may appear an odd number of times. In such cases, a frequency map or hash table is used to identify all such numbers.
Conclusion
You have successfully learned the methods to solve this problem. Now, you’re all set to help Master Remo. But, don’t just stop your learning here. There is so much more to learn.
19+ registered 
