This post is completed by 1 user Login To Mark Completed

1

Add to List Add To List..(Max 5) Close Save

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)

Run This Code

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)

Run This Code

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.

Run This Code

Code:

Output:

Element appear only once in array – 4

---

---

Also Read:

- Find longest Snake sequence in a given matrix Medium
- Given an array, find all unique subsets with a given sum with allowed repeated digits. Medium
- Find median of two sorted arrays of same size Medium
- Minimum Increments to make all array elements unique Medium
- Track the Maximum Element in a Stack. Medium
- Sort 0, 1, 2 in an array - Part 2 Beginner
- Find two smallest elements in a given array Beginner
- Rearrange the Array of Given Range N, such that A[i]=i Medium

---