This post is completed by 1 user

  • 1
 Add to List
Beginner

Find the only element in array which appears only once

Objec­tive: Given an array of integers, all the elements appear twice but one element appears only once. Write an algorithm to find that element.

Example:

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

Approach:

Brute Force:

Use nested loops and compare each element in the array with all other elements and track the element which is non-repeated.

Time Complexity: O(n^2)

Code:


Use Hashing:

·      Store the count of each element in a hash map.

·      Iterate through the hash map and return the element which has count 1.

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

Code:


Output:

Use XOR

·      We know that A XOR A = 0.

·      If we XOR all the elements in the array, all the elements which are repeated twice will become 0, and remaining will the element which is appearing only once.

Code:


Output:

Element appear only once in array – 4

Also Read: