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.

Exam­ple:

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

Approach:

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)

Code:

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)

Code:

Use XOR

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

Code:

Out­put:

Element appear only once in array – 4

You may also like...

  • Shams Mali

    int[] a = { 1, 5, 6, 2, 1, 6, 4, 3, 2, 5, 3, 1, 3, 5 };
    if (a.length == 0)
    return;
    int xor = a[0];
    for (int i = 1; i < a.length; i++) {
    xor ^= a[i];
    }
    System.out.println(“Element appear only once in array — ” + xor);

    Fails for above input and I think this algo­rithm does not work.
    Ele­ment appear only once in array — 3.

    • tuto­ri­al­hori­zon

      Your input is wrong, please read the objec­tive, it say all the ele­ments are appear­ing TWICE but one. In your input there are ele­ments which appears thrice

      • Shams Mali

        got it.

  • Shams Mali

    This is the cor­rect ver­sion of it. Your pro­gram doesn’t work and com­plex­ity is n^2 !!
    pub­lic class XOR {

    pub­lic sta­tic void main(String[] args) {
    int[] a = { 1, 5, 6, 2, 1, 6, 4, 3, 2, 5, 3, 1, 3, 5 };
    if (a.length == 0)
    return;
    for (int i = 0; i < a.length; i++) {
    for (int y = 1; y < a.length; y++) {
    if ((a[i] ^ a[y]) == 0) {
    System.out.println(a[i] + ” repeated”);
    }
    }
    }
    }
    }

    • tuto­ri­al­hori­zon

      The XOR solu­tion pro­vided has com­plex­ity O(n) (only one iter­a­tion) and the input pro­vided is wrong as per the objec­tive of the question