Find an item that appears once

Question

Find an item that appears once

Given an array where each element occurs three times, except for one element that occurs only once. Find an item that occurs once.

The expected time complexity is O (n) and O (1) extra space.

Examples:

Input: arr [] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}

Output: 2

Answer 1

If there were no O (1) space restrictions, you could go to the hash map with values ​​that are an occurrence counter.

int getUniqueElement(int[] arr) { int ones = 0 ; //At any point of time, this variable holds XOR of all the elements which have appeared "only" once. int twos = 0 ; //At any point of time, this variable holds XOR of all the elements which have appeared "only" twice. int not_threes ; for( int x : arr ) { twos |= ones & x ; //add it to twos if it exists in ones ones ^= x ; //if it exists in ones, remove it, otherwise, add it // Next 3 lines of code just converts the common 1 between "ones" and "twos" to zero. not_threes = ~(ones & twos) ;//if x is in ones and twos, dont add it to Threes. ones &= not_threes ;//remove x from ones twos &= not_threes ;//remove x from twos } return ones; } 

It mainly uses the fact that x^x = 0 and 0^x=x . Thus, all paired elements get XOR'd and disappear, leaving a lone element.

In short:

If the bit is already in one, add it to two.

XOR will add this bit to them if it is not there, or remove this bit from those if it already exists.

If the bit is in both two and two, remove it from two and two.

Upon completion, they contain bits that only appear 3 * n + 1 times, which are bits for an element that appears only once.

Answer 2

As described here , the median of array elements can be found in the worst O (n) time and O (1) optionally -space. Thus, we can solve the problem using the divide and conquer method:

Find the median in O (n) time and count the number of elements that are less than or equal to the median in O (n). If this number is 3k + 1, it means that the answer is less than or equal to the median, so omit the elements that are greater than the median in O (n). Otherwise, omit those that are less than or equal to the median. Then recursively find the answer in the remaining elements in T (n / 2). Note: the number of remaining elements is n / 2, because we omitted half the elements.

So, T (n) = T (n / 2) + O (n) = O (n), and we need O (1) extra space.

Answer 3

I am proposing a solution similar to the solution proposed by mxsekhavat. Instead of defining a median, I propose using the algorithm for breaking the Dutch national flag problem http://en.wikipedia.org/wiki/Dutch_national_flag_problem (yes, I am Dutch and was educated in Dijkstra's Style).

The result of applying the algorithm is an array separated by the red, white and blue parts. The white part can be considered the core. Please note that the white part consists of all elements equal to the axis of rotation, so the white part will consist of 1 or 3 elements. The red part consists of elements smaller than the axis of rotation, and the blue part consists of elements larger than the axis of rotation. (Note that the red and blue parts are not sorted!)

Then count the number of elements in the red, white, and blue parts. If any part consists of 1 element, then this is the number you are looking for. Otherwise, either the red or blue part consists of 3k + 1 elements for a given number k. Repeat the algorithm on the part consisting of 3k + 1 elements. In the end, one of the parts will have a size of 1.

The algorithm works in O (n) and needs O (1) variables.

Answer 4

JavaScript solution:

 function findElement(arr) { var ones = 0; var twos = 0; for (var i = 0; i < arr.length; i++) { ones = (ones ^ arr[i]) & ~twos; twos = (twos ^ arr[i]) & ~ones; } return ones; } 

Answer 5

Although the question has already been given, I found the following more intuitive and therefore adding it as an answer. Originally from here

 int singleNumber(vector<int>& nums) { /*Bits in 'ones' are set to 1, when that particular bit occurs for the first time. Bits in 'twos' are set to 1, when that particular bit occurs for the second time. If a bit is occurring for more than 2 times, we throw it away and start counting again.*/ int ones = 0; int twos = 0; for (auto elem : nums) { int onesOld = ones; /* (ones ^ elem): consider the ith bit in 'ones' be 0 (ie ith bit has not occurred till now or has occurred 2 times) and in 'elem' be 1. So, for the ith bit (ones ^ elem) gives 1. Now, ith bit could have occurred even number of times as well (ie ith bit in twos is set to 1). If that was the case, we would like to ignore such bit. This last part is taken care of by '&' with '~twos' */ ones = (ones ^ elem) & ~twos; /* (onesOld & elem) gives the bits which have occurred ones and also occur in this particular element. (twos & ~elem) gives the bits that have occurred twice and do not occur in this element. Both these cases take care of the bits that have occurred 2 times (although a bit might be set more than 2 times, like 5,7... but we take only modulo 3 count). */ twos = (onesOld & elem) | (twos & ~elem); } return ones; } 

Answer 6

Consider their binary representation and sum the number of bits in each place. For example, [1, 1, 1, 2, 2, 2, 3] gives [4, 4], given only the two bits needed to represent these numbers. If we take mode 3, we get [1,1], which in binary form is 11 = 3, which is the correct answer. This is still O (1) space because it does not scale with the number of elements, but can have a huge preliminary factor.

Some kind of sloppy cpp code:

 int l = arr.size(); int nbits = 32; vector<int> bits(nbits,0); for( int i = 0; i < l; i++ ){ for( int j = 0; j < nbits; j++ ){ bits[j] += ( A[i] >>j ) & 1; } } int missing = 0; for( int j = 0 ; j < nbits; j++ ){ if( bits[j]%3 == 1 ){ set_bit( missing, j ); } } 

It can almost certainly be optimized by people who know more about bitwise operations than I do (no one likes loops inside loops ...). In any case, I think that this should work with any problems like "k-duplicates, except for one of them", provided that the missing one appears only once.

EDIT: this answer also appears in detail here Leo Polovets https://www.quora.com/Given-an-integer-array-such-that-every-element-occurs-3-times-except-one-element- which- happens-only-once-how-do-i-find-that-singleton-in-o-1-space-and-on-time complexity

Answer 7

Add each number once and multiply the sum by 3, we get three times the sum of each element of the array. Save this as thrice_sum. Subtract the sum of the entire array from the sum of thrice_sum and divide the result by 2. The resulting number is the required number (which appears in the array once).

 def singlenumbers(arr): return (3* sum(set(arr)) - sum(arr))//2 arr = [6, 1, 3, 3, 3, 6, 6] print(singlenumbers(arr)) 

Answer 8

 def apperasonce(arr1): n=len(arr1) for i in range(0,n): if arr1.count(arr1[i]) == 1: return arr1[i] arr1=[12,1,12,3,12,1,1,2,3,3] a=apperasonce(arr1) print(a)