Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Find the only element in array which appears only once

Objec­tive: Given an array of inte­gers, all the ele­ments are appear twice but one ele­ment which appears only once. Write an algo­rithm to find that element.


int [] a = { 1,5,6,2,1,6,4,3,2,5,3};
output: 4


Brute Force:

Use nested loops and com­pare each ele­ment in array with all other ele­ments and track the ele­ment which is non-repeated.

Time Com­plex­ity: O(n^2)


Use Hash­ing:

·      Store the count of each ele­ment in a hash map.

·      Iter­ate through hash map and return the ele­ment which has count 1.

Time Com­plex­ity: O(n) , Space Com­plex­ity: O(n)



·      We know that A XOR A = 0.

·      If we XOR all the ele­ments in array, all the ele­ments which are repeated twice will become 0 and remain­ing will the ele­ment which is appear­ing only once.



Element appear only once in array – 4

You may also like...