Find all monk numbers that occur once in an array

Updated

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;
}
Output

1th Monk number is= 8
2th Monk number is= 11

Time Complexity : O(N)

Space Complexity : O(N)

Comment
Next tutorial
Mithlesh Upadhyay Published 20 Nov 2026 · 2 min read

Mithlesh Upadhyay is a Computer Science and AI expert from Madhya Pradesh with strong academic background (BE in CSE and M.Tech in AI) and over six years of experience in technical content development. He has contributed tech articles, led teams, and worked in Full Stack Development and Data Science. He founded the w3colleges.org portal for learning resources.

Related tutorials