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
- Traverse the array
- Use an Unordered Map to store the frequency of array elements.
- Traverse the Map and find the element with frequency 1 and print that element.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
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<Integer,Integer> freq = new HashMap<Integer,Integer>();
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
<script>
function CalcUnique(A, N)
{
var freq = new Map();
for (var i = 0; i < N; i++) {
if(freq.has(A[i]))
{
freq.set(A[i], freq.get(A[i])+1);
}
else
{
freq.set(A[i],1);
}
}
for (var i = 0; i < N; i++) {
if (freq.get(A[i]) == 1) {
document.write( A[i]);
return;
}
}
}
var A = [1, 1, 2, 3, 3 ];
var N = A.length;
CalcUnique(A, N);
</script>
|
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 <iostream>
#include <unordered_map>
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<Integer, Integer> freq = new HashMap<Integer, Integer>();
for (int i=0; i<N; i++)
{
int count = 1;
if(freq.containsKey(A[i]))
{
count = freq.get(A[i]);
count++;
}
freq.put(A[i], count);
}
for (int i=0; i<N; i++)
{
if (freq.get(A[i]) == 1)
{
System.out.println(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 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
<script>
function CalcUnique(A) {
let freq = A.reduce((acc, curr) => {
if (acc[curr]) {
acc[curr]++;
} else {
acc[curr] = 1;
}
return acc;
}, {});
for (let i = 0; i < A.length; i++) {
if (freq[A[i]] === 1) {
console.log(A[i]);
return;
}
}
}
const A = [1, 1, 2, 3, 3];
CalcUnique(A);
</script>
|
Time Complexity: O(N)
Auxiliary Space: O(N)