Last Updated on March 23, 2022 by Ria Pathak
CONCEPTS USED:
Hashing
DIFFICULTY LEVEL:
Easy
PROBLEM STATEMENT(
SIMPLIFIED)
:
Given an array
A
withN
integers, find thecount
of unique integers in the array.
See original problem statement here
For Example:
Input : arr = [3 2 4 1 2 3]
Output : 2
Explanation: only 1 and 4 are unique in the array rest 2, 3 are occurring 2 times.
SOLVING APPROACH:
- Initialize a temporary
Hash Array
for storing the frequency of all the elements in the array.- Traverse the array and keep incrementing the frequency of elements in the
Hash Array
.- Finally, traverse and find the
count
of all such unique elements, hence print it.
SOLUTIONS:
#includeint main() { int n; scanf("%d", &n); int arr[n]; /* hash array for storing frequency of same coloured shirts */ int hash[1001] = {0}; //count of unique shirts int count = 0; /* input the shirt and increment its frequency */ for(int i=0; i
#includeusing namespace std; int main() { int n; cin>>n; int arr[n]; /* hash array for storing frequency of same coloured shirts */ int hash[1001] = {0}; //count of unique shirts int count = 0; /* input the shirt and increment its frequency */ for(int i=0; i >arr[i]; hash[arr[i]]++; } //count all unique shirts for(int i=0; i
import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int arr[] = new int[n]; /* hash array for storing frequency of same coloured shirts */ int hash[] = new int[1001]; //count of unique shirts int count = 0; /* input the shirt and increment its frequency */ for(int i=0; i
n=int(input()) # hash array for storing frequency of same coloured shirts hash_=[0 for i in range(1001)] # count of unique shirts count=0 # input the shirt and increment its frequency arr=list(map(int,input().split())) for i in range(n): hash_[arr[i]]+=1 # count all unique shirts for i in range(n): if hash_[arr[i]]==1: count+=1 print(count)
Space Complexity :
O(N)
, due to additional Hash Array
.
[forminator_quiz id="521"]
This article tried to discuss the concept of Hashing. Hope this blog helps you understand and solve the problem. To practice more problems on Hashing you can check out MYCODE | Competitive Programming.