Single Number II

Easy

0/40

Average time to solve is 15m

Contributed by

33 upvotes

Asked in companies

Problem statement

You are given an arbitrary array ‘arr’ consisting of N non-negative integers, where every element appears thrice except one. You need to find the element that appears only once.

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

Input Format:

The first line of the input contains a single integer T, representing the number of test cases. 

The first line of each test case consists of a single integer N, representing the number of elements in the given array.

The second line of each test case contains N space-separated integers, denoting the elements of the array.

Output Format:

For each test case, print a single integer representing the element that appears only once in the array.

Note:

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

Constraints:

1 <= T <= 100
4 <= N <= 10^4
0 <= arr[i] < 10^9
Time Limit: 1sec

Sample Input 1:

1
4
1 2 1 1

Sample Output 1:

Explanation For Sample Input 1:

Clearly, the 2 appears once while 1 appears thrice. Hence, 2 is the output.

Sample Input 2:

1
7 
1 3 3 3 1 1 4

Sample Output 2:

Hint 1

Hint 2

Hint 3

Store the count of all the elements

Approaches (3)

Approach 1

Approach 2

Approach 3

Store the count of all the elements

An easy way to solve this problem is to first store the count of all the elements in a map with keys as elements of the array and value as their frequencies. Then iterate through the map to find out the element whose frequency is 1.

Time Complexity

O(N * log(N)), where N is the number of elements in the array.

Space Complexity

O(N),

Since we are using extra space for storing the count of elements in a separate data structure.

(100% EXP penalty)

Single Number II

Console