Скачать или смотреть Find the element that appears once in an array

Find the element that appears only once in a given set of integers while all the other elements occur N times.

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’.

Time Complexity: O(n)
Space Complexity: O(1)

Algorithm 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.

Time Complexity: O(n)
Space Complexity: O(1)

Code and Algorithm Visualization:
http://www.ideserve.co.in/learn/find-...

Website: http://www.ideserve.co.in

Facebook:   / ideserve.co.in