Problem

Submissions

Hints & solutions

Discuss

Single Number

Easy

0/40

Average time to solve is 10m

35 upvotes

Asked in companies

Problem statement

You are given an array A of length N, where N is always an odd integer. There are (N-1)/2 elements in the array that occur twice and one element which occurs once.

Your task is to find the only element that occurs once in the array.

Note: There are (N-1)/2+1 elements that are unique in the array.

Example:

Consider the array be 1,6,4,6,2,4,2
The integers 2, 4, 6 occur twice and only the integer 1 occurs once.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer ‘N’, representing the length of the array.

The second line contains N space-separated integers of the array A.

Output Format:

Print the only integer which occurs once in the array.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Sample Input 1:

7
7 3 5 4 5 3 4

Sample Output 1:

Explanation For Sample Input 1:

The integers 3, 4, 5 occur twice and only the integer 7 occurs once.

Sample Input 2:

9
5 6 9 6 1 9 1 5 3

Sample Output 2:

Explanation For Sample Input 2:

The integers 1, 5, 6, 9 occur twice and only the integer 3 occurs once.

Expected Time Complexity:

O(N), where ‘N’ is the length of the given array

Constraints:

1 <= N <= 10^4
-10^6 <=  A[i] <=10^6

Where T denotes the number of test cases and N denotes the length of array A[].

Time Limit: 1 sec

Hint 1

Hint 2

Think of storing frequencies.

Approaches (2)

Approach 1

Approach 2

Hashing

Explanation:

The key idea is while iterating the array count frequencies of all elements by hashing them.

And after iterating check which element occurs only once by looking at its frequency.

Algorithm:

Iterate the elements in the array.
On encounter of any element in the array increase its frequency by 1 in the hashmap.
After completion of iteration lookup into all the elements in the map and return the element with frequency as 1.

Time Complexity

O(N), where N is the length of the array

We are storing each element of the array in a hashmap. Hence the time complexity is O(N).

Space Complexity

O(N), where N is the length of the array

The memory is allocated which creating a hashmap. As there are only N elements thus it takes only O(N) space.

(100% EXP penalty)

Single Number

Console