Given an integer array such that every element occurs 3 times except one element which occurs only once, how do I find that single element in O(1) space and O(n) time complexity?

Procedure 1) Convert each number to base-3. Let's say the longest number has k digits (in base-3) 2) for all k digits, sum up all of the digits in the kth slot, and then take the result modulo 3. The resulting digits make up the element that only occurs once. Example Let's say the numbers in base-3 are: 1120121 1120121 1120121 2210022 2210022 2210022   120111 (The order they are in does not matter, so you can pretend they're not sorted) The sums of the digits in each of the 7 positions are: 9, 10, 11, 0, 4, 13, 10 if you take these modulo 3, you get: 0, 1, 2, 0, 1, 1, 1 Note that these are the base-3 digits of the un-triplicated number, so you have found your answer. Space/Time analysis Space: O(1) (that is, you only need as much space as the largest number in the list requires) Time: You're adding up N numbers which is O(N) Note that this assumes the number of digits, k, is reasonably bounded. If it's not, then the k would become a part of the big-O analyses (on the other hand, if k is bounded, we can just treat it like a constant). If k is not bounded, I don't think the problem can be solved in O(N) time and O(1) space. A simple way to understand this algorithm is to imagine that you had a list of integers, all but one of which are duplicated (instead of triplicated). To find the lone number, you could just XOR all of the input numbers, and then each number except for the lone number would be canceled out by its duplicate. This is the same idea, except in base-3 instead of base-2.

One way to do this in O(1) space & expected running time of O(n) will be to use the partitioning method as done in quick sort. The algorithm goes as Pick a random element as pivot & partition the array by it (with left side containing values less than equal to the pivot) Now check the index of pivot after partitioning say k, if k is divisible by 3 (i.e. k%3 == 0) then the unique element lies on the right otherwise on the left partition. Apply the steps 1 again on the partition you get from step 2 The amortized running time will be O(n) but worst case O(n^2), i am saying O(1) space on the assumption that reordering of the array is not an issue.

There are two approaches to this solution one as suggested by  : Here is an implementation for it : 1. One Way:  Time Complexity : O(n*log k) => where "log k" is the maximum digit of base r-radix is used to represent a repetition of a number set r-times. public class Solution { private static String computeXorBase(String firstNum, String scndNum, int radix) { int lengthFrst = firstNum.length(); int lengthscndNum = scndNum.length(); if (lengthFrst > lengthscndNum) { String swap = firstNum; firstNum = scndNum; scndNum = swap; } lengthFrst = firstNum.length(); lengthscndNum = scndNum.length(); int diffLength = lengthscndNum - lengthFrst; StringBuilder result = new StringBuilder(); for (int i = lengthFrst - 1; i >= 0; i--) { result.insert(0, (Integer.valueOf(firstNum.charAt(i) + "") + Integer.valueOf(scndNum.charAt(diffLength + i) + "")) % radix); } result.insert(0, scndNum.subSequence(0, diffLength)); return result.toString(); } private static String convertToBaseN(int num, int radix) { if (radix < 0) { radix = 10; } if (num < 0) { long l = Math.abs((long) Integer.MIN_VALUE) - Math.abs(num); l = l + 2147483648l; return Long.toString(l, radix); } else { return Integer.toString(num, radix); } } public int singleNumber(int[] A) { if (A == null || A.length <= 2) { return A[0]; } int size = A.length; int radix = 3; String result = convertToBaseN(A[0], radix); for (int i = 1; i < size; i++) { result = computeXorBase(result, convertToBaseN(A[i], radix), radix); } return (int) (long) Long.valueOf(result, radix); } } 2. Another Way: implementation in Java, public class Array3Rpt1Unq{ public static void main(String[] args) { int B[] = {2,4,4,4};//{4,4,2};//{4,4,4,2}; //bit-sets for those which are visited odd(one time only) number of times int ones = 0 ; //bit-sets for those which are visited two times. int twos = 0 ; //just to reset twos and ones if the number are visited three times int not_threes; for( int x:B ) { twos |= ones & x ; ones ^= x ; not_threes = ~(ones & twos) ; ones &= not_threes ; twos &= not_threes ; } //finally ones contains the non-repeated number printf("\n unique element = %d \n", ones ); } } Explanation : The code works in similar line with the question of "finding the element which appears once in an array - containing other elements each appearing twice". Solution is to XOR all the elements and you get the answer. Basically, it makes use of the fact that x^x = 0. So all paired elements get XOR'd and vanish leaving the lonely element. Since XOR operation is associative, commutative.. it does not matter in what fashion elements appear in array, we still get the answer. Now, in the current question - if we apply the above idea, it will not work because - we got to have every unique element appearing even number of times. So instead of getting the answer, we will end up getting XOR of all unique elements which is not what we want. To rectify this mistake, the code makes use of 2 variables. ones - At any point of time, this variable holds XOR of all the elements which have appeared "only" once. twos - At any point of time, this variable holds XOR of all the elements which have appeared "only" twice. So if at any point time, 1. A new number appears - It gets XOR'd to the variable "ones". 2. A number gets repeated(appears twice) - It is removed from "ones" and XOR'd to the variable "twice". 3. A number appears for the third time - It gets removed from both "ones" and "twice". The final answer we want is the value present in "ones" - coz, it holds the unique element. So if we explain how steps 1 to 3 happens in the code, we are done. Before explaining above 3 steps, lets look at last three lines of the code, not_threes = ~(ones & twos) ones & = not_threes twos & = not_threes All it does is, common 1's between "ones" and "twos" are converted to zero. For simplicity, in all the below explanations - consider we have got only 4 elements in the array (one unique element and 3 repeated elements - in any order). Explanation for step 1 ------------------------ Lets say a new element(x) appears. CURRENT SITUATION - Both variables - "ones" and "twos" has not recorded "x". Observe the statement "twos| = ones & x". Since bit representation of "x" is not present in "ones", AND condition yields nothing. So "twos" does not get bit representation of "x". But, in next step "ones ^= x" - "ones" ends up adding bits of "x". Thus new element gets recorded in "ones" but not in "twos". The last 3 lines of code as explained already, converts common 1's b/w "ones" and "twos" to zeros. Since as of now, only "ones" has "x" and not "twos" - last 3 lines does nothing. Explanation for step 2. ------------------------ Lets say an element(x) appears twice. CURRENT SITUATION - "ones" has recorded "x" but not "twos". Now due to the statement, "twos| = ones & x" - "twos" ends up getting bits of x. But due to the statement, "ones ^ = x" - "ones" removes "x" from its binary representation. Again, last 3 lines of code does nothing. So ultimately, "twos" ends up getting bits of "x" and "ones" ends up losing bits of "x". Explanation for step 3. ------------------------- Lets say an element(x) appears for the third time. CURRENT SITUATION - "ones" does not have bit representation of "x" but "twos" has. Though "ones & x" does not yield nothing .. "twos" by itself has bit representation of "x". So after this statement, "two" has bit representation of "x". Due to "ones^=x", after this step, "one" also ends up getting bit representation of "x". Now last 3 lines of code removes common 1's of "ones" and "twos" - which is the bit representation of "x". Thus both "ones" and "twos" ends up losing bit representation of "x".

Define a new addition  with base 3 system with no over flow  0+1 = 1, 0+2 = 2, 1+1=2,1+2=0, 2+1=0; 2+2=1.  Change all the numbers to base 3 number and add them up, you will get the number with base 3. Convert base 3 number to decimal number  example 12,4,7,4,12,12,4. Step 1: Number with 12 +4 = 110+011=121, (12+4)+7 = 121+021=112,  (12+4+7)+4=112+011=120, (12+4+7+4)+12=120+110=200, (12+4+7+4+12)+12=-200+110=010, (12+4+7+4+12+12)+4010+011=021 Step 3: Reverse transfer:021=7    So it needs constant space old sum, current number and new sum. And traverse the array only once

Input: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3} Output: 2 We can use sorting to do it in O(nLogn) time. We can also use hashing, but the worst case time complexity of hashing may be more than O(n) and hashing requires extra space. The idea is to use bitwise operators for a solution that is O(n) time and uses O(1) extra space. The solution is not easy like other XOR based solutions, because all elements appear odd number of times here. The idea is taken from http://www.careercup.com/question?id=7902674. Run a loop for all elements in array. At the end of every iteration, maintain following two values. ones: The bits that have appeared 1st time or 4th time or 7th time .. etc. twos: The bits that have appeared 2nd time or 5th time or 8th time .. etc. Finally, we return the value of ‘ones’ How to maintain the values of ‘ones’ and ‘twos’? ‘ones’ and ‘twos’ are initialized as 0. For every new element in array, find out the common set bits in the new element and previous value of ‘ones’. These common set bits are actually the bits that should be added to ‘twos’. So do bitwise OR of the common set bits with ‘twos’. ‘twos’ also gets some extra bits that appear third time. These extra bits are removed later. Update ‘ones’ by doing XOR of new element with previous value of ‘ones’. There may be some bits which appear 3rd time. These extra bits are also removed later. Both ‘ones’ and ‘twos’ contain those extra bits which appear 3rd time. Remove these extra bits by finding out common set bits in ‘ones’ and ‘twos’. #include <stdio.h> int getSingle(int arr[], int n) { int ones = 0, twos = 0 ; int common_bit_mask; // Let us take the example of {3, 3, 2, 3} to understand this for( int i=0; i< n; i++ ) { /* The expression "one & arr[i]" gives the bits that are there in both 'ones' and new element from arr[]. We add these bits to 'twos' using bitwise OR Value of 'twos' will be set as 0, 3, 3 and 1 after 1st, 2nd, 3rd and 4th iterations respectively */ twos = twos | (ones & arr[i]); /* XOR the new bits with previous 'ones' to get all bits appearing odd number of times Value of 'ones' will be set as 3, 0, 2 and 3 after 1st, 2nd, 3rd and 4th iterations respectively */ ones = ones ^ arr[i]; /* The common bits are those bits which appear third time So these bits should not be there in both 'ones' and 'twos'. common_bit_mask contains all these bits as 0, so that the bits can be removed from 'ones' and 'twos' Value of 'common_bit_mask' will be set as 00, 00, 01 and 10 after 1st, 2nd, 3rd and 4th iterations respectively */ common_bit_mask = ~(ones & twos); /* Remove common bits (the bits that appear third time) from 'ones' Value of 'ones' will be set as 3, 0, 0 and 2 after 1st, 2nd, 3rd and 4th iterations respectively */ ones &= common_bit_mask; /* Remove common bits (the bits that appear third time) from 'twos' Value of 'twos' will be set as 0, 3, 1 and 0 after 1st, 2nd, 3rd and 4th itearations respectively */ twos &= common_bit_mask; // uncomment this code to see intermediate values //printf (" %d %d \n", ones, twos); } return ones; } int main() { int arr[] = {3, 3, 2, 3}; int n = sizeof(arr) / sizeof(arr[0]); printf("The element with single occurrence is %d ", getSingle(arr, n)); return 0; } Output: 2 Time Complexity: O(n) Auxiliary Space: O(1) Implementation: http://ideone.com/sYDSKp

Here is a video on this problem:Algorithm 1: 1: Create countSetBits[] array of size 32(for representing 32 bit integer) where,  countSetBits[i] represents count of ith set bit of all elements in the input array.  Initially all elements of countSetBits[] array are 0. 2: Traverse all the elements of the input array to populate countSetBits, by doing step #3 for each of them. 3: Take the element and check for its set bits. If the ith bit is found to be set, then in the countSetBits[] array increment the count of the element at the index 'i'. 4: After finishing the above operation for all the elements of the input array, the elements of countSetBits[] would represent count of all set bits in the elements of input array. Perform the modulus N operation on each element of the countSetBits[] array. Modules N operation will eliminate count of set bits of elements occurring N times. After the modulus N operation, if we get a remainder 1 at an index 'j', then that means in the number that occurs only once, we have a set bit at index 'j'. After the modulus N operation on each element, the countSetBits[] array represents bits representation of required element. Set individual bits in variable ‘solution’.For example: Consider the array: Checkout the implementation and algorithm visualization given at this link:http://www.ideserve.co.in/learn/find-the-element-that-appears-once-in-an-arrayAlgorithm 2: 1: Initialize solution = 0. 2: Set individual bits of ‘solution’ by doing step #3. 3: To set ith bit position of ‘solution’, calculate sum of all of ith set bit of all elements in the input array, and mod it by N.Hope this helps.

A number appears three times, each bit (either 0 or 1) also appears three times. If every bit of numbers appearing three time is added, the sum of every bit should be multiple of 3.  Supposing every bit of numbers (including the unique number) in the input array is added. If the sum of a bit is multiple of 3, the corresponding bit in the unique number is 0. Otherwise, it is 1.  The solution can be implemented in Java as the code listed below: public static int FindNumberAppearingOnce(int[] numbers) { int[] bitSum = new int[32]; for(int i = 0; i < 32; ++i) { bitSum[i] = 0; } for(int i = 0; i < numbers.length; ++i) { int bitMask = 1; for(int j = 31; j >= 0; --j) { int bit = numbers[i] & bitMask; if(bit != 0) { bitSum[j] += 1; } bitMask = bitMask << 1; } } int result = 0; for(int i = 0; i < 32; ++i) { result = result << 1; result += bitSum[i] % 3; } return result; } I used to write a blog discussing this problem, and please visit http://codercareer.blogspot.kr/2013/12/no-50-numbers-appearing-once.html if you have interests.

*** UPDATE *** As pointed out by John Kurlak, the algorithm proposed below has a fatal flaw.  It won't work in certain circumstances where the triple values are divisible by 3, or the singleton is divisible by 3.  I can't think of any way to fix that without dynamically allocating some memory in order to keep track of such values, but that would violate the O(1) space constraint. ================================== 1.  Make one pass over the array, summing the positive integers into one variable, the negatives into another, and in a third variable count the zero values. 2. If the zeroes count is 1, then you are done. 3.  If not, make a second pass. During that pass, subtract each positive value from the positive sum and the see if the result is divisible by 3 (using module 3).  If it is, you've found the value.  Do the same for the negative values. This algorithm requires at most 2 passes and at best 1 pass, and so is O(n). It requires only 3 integer variables and so meets the "constant memory" requirement. It works because, if all but one values in the array exist 3 times, then subtracting the singleton from the sum will result in a sum that must be divisible by 3 (if all the values summed are of the same sign). Here's the algorithm in python: some_values = [1,4,7,13,17]   # create an array containing three of each value, and one different value (9) the_array = some_values + [9] + some_values + some_values   print the_array   # initialize the counter and accumulators sum_pos = 0 sum_neg = 0 count_zero = 0   # first pass # - sum the positive and negative values # - count the zero values for v in the_array:     if v == 0:         count_zero += 1     elif v > 0:         sum_pos += v     else:         sum_neg += v # zero test # - see if there was a single value that was zero if count_zero == 1:     print "The answer is zero"     sys.exit(0)   # initialize the answer   answer = "none found"   # second pass # - see if the sum less a single value is divisible by 3 for v in the_array:     test_pos = sum_pos - v     print "v={0:3}, sum_pos={1}, test_pos={2}, mod3={3}".format(v, sum_pos, test_pos, test_pos % 3)       if (test_pos % 3) == 0:         answer = v         break       test_neg = sum_neg - v     if (test_neg % 3) == 0:         answer = v         break         print "The answer is: ", answer Here's the output: [1, 4, 7, 13, 17, 9, 1, 4, 7, 13, 17, 1, 4, 7, 13, 17] v=  1, sum_pos=135, test_pos=134, mod3=2 v=  4, sum_pos=135, test_pos=131, mod3=2 v=  7, sum_pos=135, test_pos=128, mod3=2 v= 13, sum_pos=135, test_pos=122, mod3=2 v= 17, sum_pos=135, test_pos=118, mod3=1 v=  9, sum_pos=135, test_pos=126, mod3=0 The answer is:  9

Following is another O(n) time complexity and O(1) extra space method. We can sum the bits in same positions for all the numbers and take modulo with 3. The bits for which sum is not multiple of 3, are the bits of number with single occurrence. Let us consider the example array {5, 5, 5, 8}. The 101, 101, 101, 1000 Sum of first bits%3 = (1 + 1 + 1 + 0)%3 = 0; Sum of second bits%3 = (0 + 0 + 0 + 0)%0 = 0; Sum of third bits%3 = (1 + 1 + 1 + 0)%3 = 0; Sum of fourth bits%3 = (1)%3 = 1; Hence number which appears once is 1000