Given an array of integers, find the elements from the array whose frequency lies in the range [l, r].
Examples:
Input : arr[] = { 1, 2, 3, 3, 2, 2, 5 }
l = 2, r = 3
Output : 2 3 3 2 2
Approach :
- Take a hash map, which will store the frequency of all the elements in the array.
- Now, traverse once again.
- Print the elements whose frequency lies between the range [l, r].
C++
// C++ program to find the elements whose// frequency lies in the range [l, r]#include "iostream"#include "unordered_map"using namespace std;void findElements(int arr[], int n, int l, int r){ // Hash map which will store the // frequency of the elements of the array. unordered_map<int, int> mp; for (int i = 0; i < n; ++i) { // Increment the frequency // of the element by 1. mp[arr[i]]++; } for (int i = 0; i < n; ++i) { // Print the element whose frequency // lies in the range [l, r] if (l <= mp[arr[i]] && mp[arr[i] <= r]) { cout << arr[i] << " "; } }}int main(){ int arr[] = { 1, 2, 3, 3, 2, 2, 5 }; int n = sizeof(arr) / sizeof(arr[0]); int l = 2, r = 3; findElements(arr, n, l, r); return 0;} |
Java
import java.util.HashMap;import java.util.Map;// Java program to find the elements whose// frequency lies in the range [l, r]public class GFG { static void findElements(int arr[], int n, int l, int r) { // Hash map which will store the // frequency of the elements of the array. Map<Integer, Integer> mp = new HashMap<Integer, Integer>(); for (int i = 0; i < n; ++i) { // Increment the frequency // of the element by 1. int a=0; if(mp.get(arr[i])==null){ a=1; } else{ a = mp.get(arr[i])+1; } mp.put(arr[i], a); } for (int i = 0; i < n; ++i) { // Print the element whose frequency // lies in the range [l, r] if (l <= mp.get(arr[i]) && (mp.get(arr[i]) <= r)) { System.out.print(arr[i] + " "); } } } public static void main(String[] args) { int arr[] = {1, 2, 3, 3, 2, 2, 5}; int n = arr.length; int l = 2, r = 3; findElements(arr, n, l, r); }}/*This code is contributed by PrinciRaj1992*/ |
Python3
# Python 3 program to find the elements whose# frequency lies in the range [l, r]def findElements(arr, n, l, r): # Hash map which will store the # frequency of the elements of the array. mp = {i:0 for i in range(len(arr))} for i in range(n): # Increment the frequency # of the element by 1. mp[arr[i]] += 1 for i in range(n): # Print the element whose frequency # lies in the range [l, r] if (l <= mp[arr[i]] and mp[arr[i] <= r]): print(arr[i], end = " ") # Driver Codeif __name__ == '__main__': arr = [1, 2, 3, 3, 2, 2, 5] n = len(arr) l = 2 r = 3 findElements(arr, n, l, r) # This code is contributed by# Shashank_Sharma |
C#
// C# program to find the elements whose// frequency lies in the range [l, r]using System;using System.Collections.Generic;class GFG { static void findElements(int []arr, int n, int l, int r) { // Hash map which will store the // frequency of the elements of the array. Dictionary<int, int> mp = new Dictionary<int, int>(); for (int i = 0; i < n; ++i) { // Increment the frequency // of the element by 1. int a = 0; if(!mp.ContainsKey(arr[i])) { a = 1; } else { a = mp[arr[i]]+1; } if(!mp.ContainsKey(arr[i])) { mp.Add(arr[i], a); } else { mp.Remove(arr[i]); mp.Add(arr[i], a); } } for (int i = 0; i < n; ++i) { // Print the element whose frequency // lies in the range [l, r] if (mp.ContainsKey(arr[i]) && l <= mp[arr[i]] && (mp[arr[i]] <= r)) { Console.Write(arr[i] + " "); } } } // Driver code public static void Main(String[] args) { int []arr = {1, 2, 3, 3, 2, 2, 5}; int n = arr.Length; int l = 2, r = 3; findElements(arr, n, l, r); }}// This code has been contributed by 29AjayKumar |
Javascript
<script>// Javascript program to find the elements whose// frequency lies in the range [l, r]function findElements(arr, n, l, r) { // Hash map which will store the // frequency of the elements of the array. let mp = new Map(); for(let i = 0; i < n; ++i) { // Increment the frequency // of the element by 1. let a = 0; if (mp.get(arr[i]) == null) { a = 1; } else { a = mp.get(arr[i]) + 1; } mp.set(arr[i], a); } for(let i = 0; i < n; ++i) { // Print the element whose frequency // lies in the range [l, r] if (l <= mp.get(arr[i]) && (mp.get(arr[i]) <= r)) { document.write(arr[i] + " "); } }} // Driver Codelet arr = [ 1, 2, 3, 3, 2, 2, 5 ];let n = arr.length;let l = 2, r = 3;findElements(arr, n, l, r);// This code is contributed by code_hunt</script> |
Output
2 3 3 2 2
Time Complexity: O(N)
Auxiliary space: O(N)
Efficient Approach( Space optimization): we can use binary search . First sort the whole array for binary search function and then find frequency of all array element . Then check if the frequency of array element lies in the range [L,R]. If lies , then print that element .
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to print elements that frequency // lies in the range [L,R]void findElements(int *arr, int n , int l , int r){ sort(arr,arr+n);//sort array for binary search for(int i = 0 ; i < n ;i++) { //index of first and last occ of arr[i] using binary //search Upper and lower bound function int first_index = lower_bound(arr,arr+n,arr[i])- arr; int last_index = upper_bound(arr,arr+n,arr[i])- arr-1; int fre = last_index-first_index+1;//finding frequency if(fre >= l and fre <=r) { //printing element if its frequency lies in the range [L,R] cout << arr[i] <<" "; } } }// Drive codeint main(){ int arr[] = { 1, 2, 3, 3, 2, 2, 5 }; int n = sizeof(arr) / sizeof(arr[0]); int l = 2, r = 3; // Function call findElements( arr, n, l , r ); return 0;}// This Approach is contributed by nikhilsainiofficial546 |
Java
// Java implementation of the above approachimport java.util.*;public class FrequencyRange { // Function to print elements that frequency // lies in the range [L,R] static void findElements(int[] arr, int n, int l, int r) { Arrays.sort(arr); // sort array for binary search for (int i = 0; i < n; i++) { // index of first and last occ of arr[i] using // binary search Upper and lower bound function int first_index = Arrays.binarySearch(arr, arr[i]); int last_index = Arrays.binarySearch(arr, arr[i]); while (first_index > 0 && arr[first_index - 1] == arr[i]) { first_index--; } while (last_index < n - 1 && arr[last_index + 1] == arr[i]) { last_index++; } int fre = last_index - first_index + 1; // finding frequency if (fre >= l && fre <= r) { // printing element if its // frequency lies in the // range [L,R] System.out.print(arr[i] + " "); } } } // Driver's code public static void main(String[] args) { int[] arr = { 1, 2, 3, 3, 2, 2, 5 }; int n = arr.length; int l = 2, r = 3; // Function call findElements(arr, n, l, r); }} |
Python3
import bisect# Function to print elements whose frequency# lies in the range [L,R]def findElements(arr, n, l, r): arr.sort() # sort array for binary search for i in range(n): # index of first and last occ of arr[i] using binary # search Upper and lower bound function first_index = bisect.bisect_left(arr, arr[i]) last_index = bisect.bisect_right(arr, arr[i]) fre = last_index - first_index # finding frequency if fre >= l and fre <= r: # printing element if its frequency lies in the range [L,R] print(str(arr[i]), end = " ") print() # Driver codearr = [1, 2, 3, 3, 2, 2, 5]n = len(arr)l = 2r = 3# Function callfindElements(arr, n, l , r) |
C#
using System;class Program { static void findElements(int[] arr, int n, int l, int r) { Array.Sort(arr); // sort array for binary search for (int i = 0; i < n; i++) { // index of first and last occ of arr[i] using binary // search Upper and lower bound function int first_index = Array.BinarySearch(arr, arr[i]); while (first_index > 0 && arr[first_index - 1] == arr[i]) { first_index--; } int last_index = Array.BinarySearch(arr, arr[i]); while (last_index < n - 1 && arr[last_index + 1] == arr[i]) { last_index++; } int fre = last_index - first_index + 1; // finding frequency if (fre >= l && fre <= r) { // printing element if its frequency lies in the range [L,R] Console.Write(arr[i] + " "); } } } static void Main() { int[] arr = { 1, 2, 3, 3, 2, 2, 5 }; int n = arr.Length; int l = 2, r = 3; // Function call findElements(arr, n, l, r); }} |
Javascript
// Function to print elements that frequency // lies in the range [L,R]function findElements(arr, n, l, r) { arr.sort(); // sort array for binary search for (let i = 0; i < n; i++) { // index of first and last occ of arr[i] using binary // search Upper and lower bound function const first_index = arr.indexOf(arr[i]); const last_index = arr.lastIndexOf(arr[i]); const fre = last_index - first_index + 1; // finding frequency if (fre >= l && fre <= r) { // printing element if its frequency lies in the range [L,R] console.log(arr[i] + " "); } } }// Drive codeconst arr = [1, 2, 3, 3, 2, 2, 5];const n = arr.length;const l = 2;const r = 3;// Function callfindElements(arr, n, l , r); |
Output
2 2 2 3 3
Time Complexity: O(N*Log2N)
Auxiliary space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
