Question

Given an array of 13 elements ,4 array elements occurs thrice in arraya, find the element occurs array only once

Answer 1

Answer:

Given an array of integers. All numbers occur twice except one number which occurs once. Find the number in O(n) time & constant extra space.

Example :

Input: ar[] = {7, 3, 5, 4, 5, 3, 4}

Output: 7

One solution is to check every element if it appears once or not. Once an element with single occurrence is found, return it. Time complexity of this solution is O(n2).

A better solution is to use hashing.

1) Traverse all elements and put them in a hash table. Element is used as key and count of occurrences is used as value in hash table.

2) Traverse the array again and print the element with count 1 in hash table.

This solution works in O(n) time, but requires extra space.