# Find the only non-repeating element in a given array

Improve Article

Save Article

Improve Article

Save Article

Given an array A[] consisting of N (1 ≤ N ≤ 105) positive integers, the task is to find the only array element with a single occurrence.

Note: It is guaranteed that only one such element exists in the array.

Examples:

Input: A[] = {1, 1, 2, 3, 3}
Output: 2
Explanation:
Distinct array elements are {1, 2, 3}.
Frequency of these elements are {2, 1, 2} respectively.

Input : A[] = {1, 1, 1, 2, 2, 3, 5, 3, 4, 4}
Output : 5

Approach: Follow the steps below to solve the problem

1. Traverse the array
2. Use an Unordered Map to store the frequency of array elements.
3. Traverse the Map and find the element with frequency 1 and print that element.

Below is the implementation of the above approach:

## C++

 `#include ` `using` `namespace` `std;` `void` `CalcUnique(``int` `A[], ``int` `N)` `{` `    ` `    ` `    ``unordered_map<``int``, ``int``> freq;` `    ` `    ``for` `(``int` `i = 0; i < N; i++) {` `        ` `        ``freq[A[i]]++;` `    ``}` `    ` `    ``for` `(``int` `i = 0; i < N; i++) {` `        ` `        ` `        ``if` `(freq[A[i]] == 1) {` `            ``cout << A[i];` `            ``return``;` `        ``}` `    ``}` `}` `int` `main()` `{` `    ``int` `A[] = { 1, 1, 2, 3, 3 };` `    ``int` `N = ``sizeof``(A) / ``sizeof``(A[0]);` `    ``CalcUnique(A, N);` `    ``return` `0;` `}`

## Java

 `import` `java.util.*;` `class` `GFG` `{` `  ` `  ` `  ``static` `void` `CalcUnique(``int` `A[], ``int` `N)` `  ``{` `    ` `    ` `    ``HashMap freq = ``new` `HashMap();` `    ` `    ``for` `(``int` `i = ``0``; i < N; i++)` `    ``{` `      ` `      ``if``(freq.containsKey(A[i]))` `      ``{` `        ``freq.put(A[i], freq.get(A[i]) + ``1``);` `      ``}` `      ``else` `      ``{` `        ``freq.put(A[i], ``1``);` `      ``}` `    ``}` `    ` `    ``for` `(``int` `i = ``0``; i < N; i++)` `    ``{` `      ` `      ` `      ``if` `(freq.containsKey(A[i])&&freq.get(A[i]) == ``1``)` `      ``{` `        ``System.out.print(A[i]);` `        ``return``;` `      ``}` `    ``}` `  ``}` `  ` `  ``public` `static` `void` `main(String[] args)` `  ``{` `    ``int` `A[] = { ``1``, ``1``, ``2``, ``3``, ``3` `};` `    ``int` `N = A.length;` `    ``CalcUnique(A, N);` `  ``}` `}`

## Python3

 `from` `collections ``import` `defaultdict` `def` `CalcUnique(A, N):` `    ` `    ` `    ``freq ``=` `defaultdict(``int``)` `    ` `    ``for` `i ``in` `range``(N):` `        ` `        ``freq[A[i]] ``+``=` `1` `    ` `    ``for` `i ``in` `range``(N):` `        ` `        ` `        ``if` `(freq[A[i]] ``=``=` `1``):` `            ``print``(A[i])` `            ``return` `if` `__name__ ``=``=` `"__main__"``:` `    ``A ``=` `[``1``, ``1``, ``2``, ``3``, ``3``]` `    ``N ``=` `len``(A)` `    ``CalcUnique(A, N)` `    `

## C#

 `using` `System;` `using` `System.Collections.Generic;` `public` `class` `GFG` `{` `  ` `  ` `  ``static` `void` `CalcUnique(``int` `[]A, ``int` `N)` `  ``{` `    `  `    ` `    ` `    ``Dictionary<``int``,``int``> freq = ``new` `Dictionary<``int``,``int``>();` `    ` `    ``for` `(``int` `i = 0; i < N; i++)` `    ``{` `      ` `      ``if``(freq.ContainsKey(A[i]))` `      ``{` `        ``freq[A[i]] = freq[A[i]] + 1;` `      ``}` `      ``else` `      ``{` `        ``freq.Add(A[i], 1);` `      ``}` `    ``}` `    ` `    ``for` `(``int` i = 0; i < N; i++) `    ``{` `      ` `      ` `      ``if` `(freq.ContainsKey(A[i]) && freq[A[i]] == 1)` `      ``{` `        ``Console.Write(A[i]);` `        ``return``;` `      ``}` `    ``}` `  ``}` `  ` `  ``public` `static` `void` `Main(String[] args)` `  ``{` `    ``int` `[]A = { 1, 1, 2, 3, 3 };` `    ``int` `N = A.Length;` `    ``CalcUnique(A, N);` `  ``}` `}`

## Javascript

 ``
Output:

`2`

Time Complexity : O(N)
Auxiliary Space : O(N)

#### Another Approach: Using Built-in  Functions:

• Calculate the frequencies using Built-In function.
• Traverse the array and find the element with frequency 1 and print it.

Below is the implementation:

## C++

 `#include ` `#include ` `using` `namespace` `std;` `void` `CalcUnique(``int` `A[], ``int` `N)` `{` `  ` `  ``unordered_map<``int``, ``int``> freq;` `  ` `  ``for` `(``int` `i = 0; i < N; i++)` `  ``{` `    ` `    ``int` `count = 1;` `    ``if` `(freq.count(A[i])) {` `      ``count = freq[A[i]];` `      ``count++;` `    ``}` `    ``freq[A[i]] = count;` `  ``}` `  ` `  ``for` `(``int` `i = 0; i < N; i++)` `  ``{` `    ` `    ``if` `(freq[A[i]] == 1) {` `      ``cout << A[i] << endl;` `      ``return``;` `    ``}` `  ``}` `}` `int` `main()` `{` `  ``int` `A[] = { 1, 1, 2, 3, 3 };` `  ``int` `N = ``sizeof``(A) / ``sizeof``(A[0]);` `  ``CalcUnique(A, N);` `  ``return` `0;` `}`

## Java

 `import` `java.util.Map;` `import` `java.util.HashMap;` `class` `Main{` `public` `static` `void` `CalcUnique(``int` `A[], ``int` `N)` `{` `    ` `    ` `    ``Map freq = ``new` `HashMap();` `    `  `    ` `    ``for` `(``int` `i=``0``; i

## Python3

 `from` `collections ``import` `Counter` `def` `CalcUnique(A, N):` `    ` `    ` `    ``freq ``=` `Counter(A)` `    `  `    ` `    ``for` `i ``in` `A:` `        ` `        ` `        ``if` `(freq[i] ``=``=` `1``):` `            ``print``(i)` `            ``return` `if` `__name__ ``=``=` `"__main__"``:` `    ``A ``=` `[1, 1, 2, 3, 3]````     N = len(A)     CalcUnique(A, N) `````` ```

## C#

 `using` `System;` `using` `System.Collections.Generic;` `public` `class` `MainClass {` `  ` `  ` `  ``static` `void` `CalcUnique(``int``[] A, ``int` `N)` `  ``{` `    ` `    ``Dictionary<``int``, ``int``> freq` `      ``= ``new` `Dictionary<``int``, ``int``>();` `    ` `    ``for` `(``int` `i = 0; i < N; i++) {` `      ` `      ` `      ``if` `(freq.ContainsKey(A[i])) {` `        ``freq[A[i]]++;` `      ``}` `      ``else` `{` `        ``freq[A[i]] = 1;` `      ``}` `    ``}` `    ` `    ``for` `(``int` `i = 0; i < N; i++) {` `      ` `      ``if` `(freq[A[i]] == 1) {` `        ``Console.WriteLine(A[i]);` `        ``return``;` `      ``}` `    ``}` `  ``}` `  ` `  ``public` `static` `void` `Main()` `  ``{` `    ``int``[] A = { 1, 1, 2, 3, 3 };` `    ``int` `N = A.Length;` `    ``CalcUnique(A, N);` `  ``}` `}`

## Javascript

 ``

Time Complexity: O(N)
Auxiliary Space: O(N)