Problem Statement: Find the two numbers which occur an odd number of times in the given unsorted array.
Examples:
Example 1:
Input: N = 8, array[] = {5 , 5 , 2 , 8 , 1 , 8, 1 , 1}
Output: 2 , 1
Explanation: The two numbers 2 and 1 only occur an odd number of times. Rest of the number occurs even number of times.
Example 2:
Input: N = 5, array[] = {10 , 7 , 6 , 6 , 6 , 6, 7 , 4}
Output: 4 , 10
Explanation: The two numbers 10 and 4 only occur an odd number of times. Rest of the number occurs even number of times.
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1: Using unordered_map
Approach:
Store the frequency of all the elements in the map
Now run a for loop and check if any element frequency occurs an odd number of times in the map and print it.
Code:
C++ Code
#include "bits/stdc++.h"
using namespace std;
vector < int > two_odd(int nums[], int n) {
unordered_map < int, int > mp;
for (int i = 0; i < n; ++i) {
++mp[nums[i]];
}
cout << "Two numbers with odd occurrences are: ";
vector < int > ans;
for (auto & x: mp) {
if (x.second % 2 == 1) {
ans.push_back(x.first);
}
}
return ans;
}
int main() {
int nums[] = {5,5,2,8,1,8,1,1};
int n = sizeof(nums) / sizeof(nums[0]);
vector < int > ans = two_odd(nums, n);
for (int i = 0; i < ans.size(); ++i) {
cout << ans[i] << ", ";
}
return 0;
}Output: Two numbers with odd occurrences are: 1, 2.
Time Complexity: O(n).
Space Complexity: O(n).
Java Code
import java.util.*;
class Main {
static void two_odd(int nums[], int nums_size) {
HashMap < Integer, Integer > mp = new HashMap < Integer, Integer > ();
for (int i = 0; i < nums_size; ++i) {
if (mp.containsKey(nums[i])) {
mp.put(nums[i], mp.get(nums[i]) + 1);
} else {
mp.put(nums[i], 1);
}
}
System.out.print("Two numbers with odd occurrences are: ");
for (Map.Entry < Integer, Integer > x: mp.entrySet()) {
if (x.getValue() % 2 == 1) {
System.out.print(x.getKey() + ", ");
}
}
}
public static void main(String args[]) {
int nums[] = {5,5,2,8,1,8,1,1};
two_odd(nums, nums.length);
}
}Output: Two numbers with odd occurrences are: 1, 2.
Time Complexity: O(n).
Space Complexity: O(n).
Python Code
def two_odd(nums):
nums.sort()
mp = {}
for i in nums:
if i not in mp:
mp[i] = 0
mp[i] += 1
print("Two numbers with odd occurrences are: ", end = " ")
for x in mp:
if (mp[x] % 2 == 1):
print(x, end = ", ")
nums = [5, 5, 2, 8, 1, 8, 1, 1]
two_odd(nums)Output: Two numbers with odd occurrences are: 1, 2.
Time Complexity: O(n).
Space Complexity: O(n).
Solution 2: XOR-based solution.
Prerequisite:-
Some basic xor properties:
- XOR of same number gives 0 (n^n = 0)
- XOR of 0 with any number gives 0 (n^0 = 0)
- XOR obey Commutative property (a^b = b^a)
- XOR obey Associative property a^(b^c) = (a^b)^c
Approach:
- Take XOR of all the elements in the given array. Take XOR for all the elements in the given array and save it in some variable, say x. now all the elements which occur an even number of times will automatically cancel out based on a property (n^n=0). Now the variable x contains only the XOR of two numbers which occur an odd number of times.
Example:- nums[ ] = {5 , 5 , 2 , 8 , 1 , 8 , 1 , 1}
After step 1 the variable x contains (2^1) x=3.
- Extract leftmost set bit in x. To Extract leftmost set bit:- (x & ~(x-1)) (observation based property)
- Separate two odd occurring elements in two different group. Take AND of all the elements in the given array with set_bit, the result will give either 0 or 1. put all the elements which give the result 1 in one group and zero in another group. The two odd occurring elements must lie in a different group because for a selected set bit index in x the two odd occurring elements must have different values. Now the question boils down to find the single number which occurs an odd number of times in a group. ByTaking XOR for all the elements which are in the same group we can get the two odd occurring elements.
Code:
C++ Code
#include "bits/stdc++.h"
using namespace std;
vector < int > two_odd(int nums[], int n) {
int x = 0;
for (int i = 0; i < n; ++i) {
x ^= nums[i];
}
int set_bit;
set_bit = x & (~(x - 1));
int first = 0, second = 0;
for (int i = 0; i < n; ++i) {
if (nums[i] & set_bit) {
first ^= nums[i];
} else second ^= nums[i];
}
return {
first,
second
};
}
int main() {
int nums[] = {5, 5, 2, 8, 1, 8, 1, 1};
int n = sizeof(nums) / sizeof(nums[0]);
vector < int > ans = two_odd(nums, n);
cout << "Two numbers with odd occurrences are: ";
for (int i = 0; i < ans.size(); ++i) {
cout << ans[i] << ",";
}
return 0;
}Output: Two numbers with odd occurrences are: 1,2,
Time complexity:O(n)
Space complexity:O(1)
Java Code
import java.util.*;
class Main {
static void two_odd(int nums[], int nums_size) {
int x = 0;
for (int i = 0; i < nums_size; ++i) {
x ^= nums[i];
}
int set_bit;
set_bit = x & ~(x - 1);
int first = 0, second = 0;
for (int i = 0; i < nums_size; ++i) {
if ((nums[i] & set_bit) > 0) {
first ^= nums[i];
} else second ^= nums[i];
}
System.out.println("Two numbers with odd occurrences are: " + first + " ,
" + second);
}
public static void main(String[] args) {
int nums[] = {5, 5, 2, 8, 1, 8, 1, 1};
two_odd(nums, nums.length);
}
}Output: Two numbers with odd occurrences are: 1,2,
Time complexity:O(n)
Space complexity:O(1)
Python Code
def two_odd(nums, nums_size):
x = 0
for i in nums:
x = x ^ i
set_bit = x & ~(x - 1)
first, second = 0, 0
for i in range(nums_size):
if (nums[i] & set_bit):
first = first ^ nums[i]
else :
second = second ^ nums[i]
print("Two numbers with odd occurrences are: ", first, ",", second)
nums = [5, 5, 2, 8, 1, 8, 1, 1]
two_odd(nums, len(nums))Output: Two numbers with odd occurrences are: 1,2,
Time complexity:O(n)
Space complexity:O(1)
Special thanks to JAIGANESH R S for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article