Map O(n) time and O(n) extra space solution using C

Software Development
#1

Hello Folks,

The extra space O(n) can be minimized to O(1) by directly taking inputs in map instead of array. Look for the picked element in hash table. If the element is found in hash table, increment its count in table. If the element is not found, then enter it in hash table with count as 1. After all elements are entered in hash table, scan the hash table and print elements with odd count. This approach may take O(n) time on average, but it requires O(n) extra space.
Let the two odd occurring numbers be x and y. We use bitwise XOR to get x and y. The first step is to do XOR of all elements present in array. XOR of all elements gives us XOR of x and y because of the following properties of XOR operation.

XOR of any number n with itself gives us 0, i.e., n ^ n = 0
XOR of any number n with 0 gives us n, i.e., n ^ 0 = n
XOR is cumulative and associative.
So we have XOR of x and y after the first step. Let the value of XOR be xor2. Every set bit in xor2 indicates that the corresponding bits in x and y have values different from each other. For example, if x = 6 (0110) and y is 15 (1111), then xor2 will be (1001), the two set bits in xor2 indicate that the corresponding bits in x and y are different. In the second step, we pick a set bit of xor2 and divide array elements in two groups. Both x and y will go to different groups. In the following code, the rightmost set bit of xor2 is picked as it is easy to get rightmost set bit of a number. If we do XOR of all those elements of array which have the corresponding bit set (or 1), then we get the first odd number. And if we do XOR of all those elements which have the corresponding bit 0, then we get the other odd occurring number. This step works because of the same properties of XOR. All the occurrences of a number will go in same set. XOR of all occurrences of a number which occur even number of times will result in 0 in its set. And the xor of a set will be one of the odd occurring elements.

Given an unsorted array that contains even number of occurrences for all numbers except two numbers. Find the two numbers which have odd occurrences in O(n) time complexity and O(1) extra space.

Examples:

Input: {12, 23, 34, 12, 12, 23, 12, 45}
Output: 34 and 45

Input: {4, 4, 100, 5000, 4, 4, 4, 4, 100, 100}
Output: 100 and 5000

Input: {10, 20}
Output: 10 and 20

The idea is explained below using comments in code-

  • C

#include <bits/stdc++.h>

using namespace std;

/* Prints two numbers that occur odd number of times. The

function assumes that the array size is at least 2 and

there are exactly two numbers occurring odd number of times.

*/

void printTwoOdd( int arr[], int size)

{

`` /*Create map and calculate frequency of array of

`` * elements using array.*/

`` map< int , int > m;

`` for ( int i = 0; i < size; i++) {

`` m[arr[i]]++;

`` }

`` /*Traverse through the map and check if its second

`` element that is the frequency is odd or not.Then this

`` is the odd occuring element .Its is clearly mentioned

`` in problem that there are only two odd occuring

`` elements so this will print those two elements.*/

`` cout << "The two ODD elements are " ;

`` for ( auto & x : m) {

`` if (x.second % 2 != 0)

`` cout << x.first << ", " ;

`` }

}

/* Driver code */

int main()

{

`` int arr[] = { 4, 2, 4, 5, 2, 3, 3, 1 };

`` int arr_size = sizeof (arr) / sizeof (arr[0]);

`` printTwoOdd(arr, arr_size);

`` return 0;

}

Output

The two ODD elements are 1, 5,

Time Complexity: O(n)

Auxiliary Space: O(n)