Given an array arr of positive numbers of size N. Our task is to print all the monk numbers in the array. An element is monk number if it has occurred only once in the array and its adjacent numbers (previous and next) are both not present in the array.
Examples :
Input array: {2, 5, 6, 1, 8, 11, 3}
Output : {8, 11}
Explanation :
8 is monk number cause it has occurred once and both 7 and 9 are not
present in array.
Input array: {3, 5, 7, 1, 8, 5, 3}
Output : {1}
Explanation :
3 and 5 have appeared twice, so not a monk number.
7 & 8 are adjacent numbers, so neither is a monk number.
1 is monk number, cause its adjacent numbers are not present and it
appeared once.
Approach :
The idea is to use the hashmap. The hashmap will store the frequency of each element appearing in the array. Traverse the hashmap from left to right and push the element into monk vector if the frequency of previous and next elements are zero. This approach takes linear time.
Below is the code implementation :
//Program for above approach.
#include <bits/stdc++.h>
using namespace std;
//Utility function.
vector<int> FindMonkNumber(vector<int>& nums)
{
map<int,int> m;
vector<int> monk;
for(int i=0;i<nums.size();i++)
{
m[nums[i]]++;
}
for(int i=0;i<nums.size();i++)
{
if(m[nums[i]]==1)
{
if(m[nums[i]+1]==0 && m[nums[i]-1]==0)
{
monk.push_back(nums[i]);
}
}
}
return monk;
}
//Main function
int main() {
vector <int> monk, arr {2, 5, 6, 1, 8, 11, 3};
monk=FindMonkNumber(arr);
int i=1;
for(auto it: monk)
cout<<i++<<"th Monk number is= "<<it<<"\n";
return 0;
}
Time Complexity : O(N)
Space Complexity : O(N)