Given a vector vec, and a integer K the task is to count the number of elements such that it occurs only once in the vector and with the number Kth times less and more is not present in the vector. For example: if 9 is present in the vector and K=3 then, 6 and 12 should not be present in the vector.
Examples: Input: vec = {1,2,5,8,9} K=1 Output: 1 Explanation: We traverse the array and for each element we check both the conditions that is if the frequency of the element in the array is one and if the Kth number less than and more than the current are not present in the vector. For 1 and K=1, since 2 is present it fails the condition For 2 and K=1,1 will be the predecessor it also fails the condition. 5 satisfies both the conditions and hence we increase the count by 1 which was initially zero. Similarly for 8 and 9 they are adjacent hence fail the condition. Hence only 5 satisfies the given conditions and the count will be 1. Input: vec = {2,2,4,6,9,13} K=2 Output: 2 Explanation: We traverse the array and for each element we check both the conditions that is if the frequency of the element in the array is one and if the Kth number less than and more than the current are not present in the vector. For 2 the frequency in the vector is 2 hence it fails the condition. For 4 with K=2, 2 as well as 6 is present in the vector hence it fails the condition For 6 with K=2, 4 is present in the vector hence it also fails For 9 and 13 both the conditions are satisfied hence the count is increased to 2. Hence the final count will by 2
Approach:
We first create a map and store the frequency of each element in the map.
Then as we keep traversing the vector we check simultaneously if the frequency of the element is equal to 1 and if the Kth number less than or more than the current element don’t occur in the vector. For example if vec[i]=17 and K=7, then 10 and 24 should not be present in the vector.
Below is the implementation of the above approach:
#include <bits/stdc++.h> using namespace std; int countElementsWhichSatisfy(vector<int>& vec, int K) { // creating a map to check frequency of each element map<int, int> mp; // run the loop for (int i = 0; i < vec.size(); i++) { // insert in map. mp[vec[i]]++; } // counter variable to count number of elements which // satisfy the conditons int ctr = 0; // run the loop for (int i = 0; i < vec.size(); i++) { // check frequency is 1 only that is mp[vec[i]] == 1 // check whole map and see whether Kth number less // or more than the current element is not present // in the vector mp.find(vec[i]-K) == mp.end() and // mp.find(vec[i]+K) == mp.end() if (mp[vec[i]] == 1 and mp.find(vec[i] - K) == mp.end() and mp.find(vec[i] + K) == mp.end()) { // increase counter variable by 1 ctr++; } } // return the counter value return ctr; } int main() { vector<int> vec = { 2, 2, 4, 6, 9, 13 }; int K = 2; cout << countElementsWhichSatisfy(vec, K) << endl; }
Output:
2
Time Complexity: O(N)
Auxiliary Space: O(1)