Count all elements in the array which appears at least K times after their first occurrence
Given an array arr[] of N integer elements and an integer K. The task is to count all distinct arr[i] such that arr[i] appears at least K times in the index range i + 1 to n – 1.
Examples:
Input: arr[] = {1, 2, 1, 3}, K = 1
Output: 1
arr[0] = 1 is the only element that appears at least once in the index range [1, 3] i.e. arr[2]Input: arr[] = {1, 2, 3, 2, 1, 3, 1, 2, 1}, K = 2
Output: 2
Naive Approach: Start from i = 0 to n-1, count occurrences of arr[i] in range i+1 to n-1. If the count is greater or equal to K, increment result by 1. Make a hash array to avoid duplicates.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <iostream> #include <map> using namespace std; // Function to return the count of // all distinct valid elements int countOccurrence( int n, int arr[], int k) { int cnt, ans = 0; // To avoid duplicates map< int , bool > hash; // Traverse the complete array for ( int i = 0; i < n; i++) { cnt = 0; // If current element is previously checked // don't check it again if (hash[arr[i]] == true ) continue ; // To avoid duplicates hash[arr[i]] = true ; // Count occurrence of arr[i] in range [i + 1, n - 1] for ( int j = i + 1; j < n; j++) { if (arr[j] == arr[i]) cnt++; // If count becomes equal to K // break the loop if (cnt >= k) break ; } // If cnt >= K // increment ans by 1 if (cnt >= k) ans++; } return ans; } // Driver code int main() { int arr[] = { 1, 2, 1, 3 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 1; cout << countOccurrence(n, arr, k); return 0; } |
Java
// Java implementation of the approach import java.util.HashMap; class GFG { // Function to return the count of // all distinct valid elements public static int countOccurrence( int n, int [] arr, int k) { int cnt, ans = 0 ; // To avoid duplicates HashMap<Integer, Boolean> hash = new HashMap<>(); // Traverse the complete array for ( int i = 0 ; i < n; i++) { cnt = 0 ; // If current element is previously checked // don't check it again if (hash.get(arr[i]) != null && hash.get(arr[i]) == true ) continue ; // To avoid duplicates hash.put(arr[i], true ); // Count occurrence of arr[i] in range [i + 1, n - 1] for ( int j = i + 1 ; j < n; j++) { if (arr[j] == arr[i]) cnt++; // If count becomes equal to K // break the loop if (cnt >= k) break ; } // If cnt >= K // increment ans by 1 if (cnt >= k) ans++; } return ans; } // Driver Code public static void main(String[] args) { int [] arr = { 1 , 2 , 1 , 3 }; int n = arr.length; int k = 1 ; System.out.println(countOccurrence(n, arr, k)); } } // This code is contributed by // sanjeev2552 |
Python3
# Python3 implementation of the approach # Function to return the count of # all distinct valid elements def countOccurrence(n, arr, k): cnt, ans = 0 , 0 # To avoid duplicates Hash = dict () # Traverse the complete array for i in range (n): cnt = 0 # If current element is previously # checked don't check it again if (arr[i] in Hash .keys()): continue # To avoid duplicates Hash [arr[i]] = 1 # Count occurrence of arr[i] in # range [i + 1, n - 1] for j in range (i + 1 , n): if (arr[j] = = arr[i]): cnt + = 1 # If count becomes equal to K # break the loop if (cnt > = k): break # If cnt >= K # increment ans by 1 if (cnt > = k): ans + = 1 return ans # Driver code arr = [ 1 , 2 , 1 , 3 ] n = len (arr) k = 1 print (countOccurrence(n, arr, k)) # This code is contributed # by mohit kumar |
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // Function to return the count of // all distinct valid elements public static int countOccurrence( int n, int [] arr, int k) { int cnt, ans = 0; // To avoid duplicates Dictionary< int , Boolean> hash = new Dictionary< int , Boolean>(); // Traverse the complete array for ( int i = 0; i < n; i++) { cnt = 0; // If current element is previously checked // don't check it again if (hash.ContainsKey(arr[i]) && hash[arr[i]] == true ) continue ; // To avoid duplicates hash.Add(arr[i], true ); // Count occurrence of arr[i] // in range [i + 1, n - 1] for ( int j = i + 1; j < n; j++) { if (arr[j] == arr[i]) cnt++; // If count becomes equal to K // break the loop if (cnt >= k) break ; } // If cnt >= K // increment ans by 1 if (cnt >= k) ans++; } return ans; } // Driver Code public static void Main(String[] args) { int [] arr = {1, 2, 1, 3}; int n = arr.Length; int k = 1; Console.WriteLine(countOccurrence(n, arr, k)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript implementation of the approach // Function to return the count of // all distinct valid elements function countOccurrence(n, arr, k) { let cnt, ans = 0; // To avoid duplicates let hash = new Map(); // Traverse the complete array for (let i = 0; i < n; i++) { cnt = 0; // If current element is previously checked // don't check it again if (hash.get(arr[i]) != null && hash.get(arr[i]) == true ) continue ; // To avoid duplicates hash.set(arr[i], true ); // Count occurrence of arr[i] // in range [i + 1, n - 1] for (let j = i + 1; j < n; j++) { if (arr[j] == arr[i]) cnt++; // If count becomes equal to K // break the loop if (cnt >= k) break ; } // If cnt >= K // increment ans by 1 if (cnt >= k) ans++; } return ans; } // Driver code let arr = [1, 2, 1, 3]; let n = arr.length; let k = 1; document.write(countOccurrence(n, arr, k)); </script> |
1
Time Complexity: O(n2*log(n))
Auxiliary Space: O(n), where n is the size of the given array.
Efficient Approach: Declare another hash map to store the occurrence of all elements and start from n – 1 to 0. If occurrence[arr[i]] ? k then increment the count by 1 otherwise increment occurrence of arr[i] by 1.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <iostream> #include <map> using namespace std; // Function to return the count of // all distinct valid elements int countOccurrence( int n, int arr[], int k) { int cnt, ans = 0; // To avoid duplicates map< int , bool > hash; // To store the count of arr[i] // in range [i + 1, n - 1] map< int , int > occurrence; for ( int i = n - 1; i >= 0; i--) { // To avoid duplicates if (hash[arr[i]] == true ) continue ; // If occurrence in range i+1 to n becomes // equal to K then increment ans by 1 if (occurrence[arr[i]] >= k) { ans++; hash[arr[i]] = true ; } // Otherwise increase occurrence of arr[i] by 1 else occurrence[arr[i]]++; } return ans; } // Driver code int main() { int arr[] = { 1, 2, 1, 3 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 1; cout << countOccurrence(n, arr, k); return 0; } |
Java
// Java implementation of the approach import java.util.HashMap; class GFG { // Function to return the count of // all distinct valid elements public static int countOccurrence( int n, int [] arr, int k) { int ans = 0 ; // To avoid duplicates HashMap<Integer, Boolean> hash = new HashMap<>(); // To store the count of arr[i] // in range [i + 1, n - 1] HashMap<Integer, Integer> occurrence = new HashMap<>(); for ( int i = n- 1 ; i>= 0 ; i--) { // To avoid duplicates if (hash.get(arr[i]) != null && hash.get(arr[i]) == true ) continue ; // If occurrence in range i+1 to n becomes // equal to K then increment ans by 1 if (occurrence.get(arr[i]) != null && occurrence.get(arr[i]) >= k) { ans++; hash.put(arr[i], true ); } // Otherwise increase occurrence of arr[i] by 1 else { if (occurrence.get(arr[i]) == null ) occurrence.put(arr[i], 1 ); else { int temp = occurrence.get(arr[i]); occurrence.put(arr[i], ++temp); } } } return ans; } // Driver Code public static void main(String[] args) { int [] arr = { 1 , 2 , 1 , 3 }; int n = arr.length; int k = 1 ; System.out.println(countOccurrence(n, arr, k)); } } // This code is contributed by // sanjeev2552 |
Python3
# Python3 implementation of the approach # Function to return the count of # all distinct valid elements def countOccurrence(n, arr, k) : ans = 0 ; # To avoid duplicates hash = dict .fromkeys(arr, 0 ); # To store the count of arr[i] # in range [i + 1, n - 1] occurrence = dict .fromkeys(arr, 0 ); for i in range (n - 1 , - 1 , - 1 ) : # To avoid duplicates if ( hash [arr[i]] = = True ) : continue ; # If occurrence in range i+1 to n # becomes equal to K then increment # ans by 1 if (occurrence[arr[i]] > = k) : ans + = 1 ; hash [arr[i]] = True ; # Otherwise increase occurrence # of arr[i] by 1 else : occurrence[arr[i]] + = 1 ; return ans; # Driver code if __name__ = = "__main__" : arr = [ 1 , 2 , 1 , 3 ]; n = len (arr) ; k = 1 ; print (countOccurrence(n, arr, k)); # This code is contributed by Ryuga |
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // Function to return the count of // all distinct valid elements public static int countOccurrence( int n, int [] arr, int k) { int ans = 0; // To avoid duplicates Dictionary< int , bool > hash = new Dictionary< int , bool >(); // To store the count of arr[i] // in range [i + 1, n - 1] Dictionary< int , int > occurrence = new Dictionary< int , int >(); for ( int i = n - 1; i >= 0; i--) { // To avoid duplicates if (hash.ContainsKey(arr[i]) && hash[arr[i]] == true ) continue ; // If occurrence in range i+1 to n becomes // equal to K then increment ans by 1 if (occurrence.ContainsKey(arr[i]) && occurrence[arr[i]] >= k) { ans++; hash.Add(arr[i], true ); } // Otherwise increase occurrence of arr[i] by 1 else { if (!occurrence.ContainsKey(arr[i])) occurrence.Add(arr[i], 1); else { int temp = occurrence[arr[i]]; occurrence.Add(arr[i], ++temp); } } } return ans; } // Driver Code public static void Main(String[] args) { int [] arr = {1, 2, 1, 3}; int n = arr.Length; int k = 1; Console.WriteLine(countOccurrence(n, arr, k)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript implementation of the approach // Function to return the count of // all distinct valid elements function countOccurrence(n, arr, k) { let ans = 0; // To avoid duplicates let hash = new Map(); // To store the count of arr[i] // in range [i + 1, n - 1] let occurrence = new Map(); for (let i = n - 1; i >= 0; i--) { // To avoid duplicates if (hash.get(arr[i]) != null && hash.get(arr[i]) == true ) continue ; // If occurrence in range i+1 to n becomes // equal to K then increment ans by 1 if (occurrence.get(arr[i]) != null && occurrence.get(arr[i]) >= k) { ans++; hash.set(arr[i], true ); } // Otherwise increase occurrence of arr[i] by 1 else { if (occurrence.get(arr[i]) == null ) occurrence.set(arr[i], 1); else { let temp = occurrence.get(arr[i]); occurrence.set(arr[i], ++temp); } } } return ans; } // Driver Code let arr = [ 1, 2, 1, 3 ]; let n = arr.length; let k = 1; document.write(countOccurrence(n, arr, k)); // This code is contributed by unknown2108 </script> |
1
Time Complexity: O(n)
Auxiliary Space: O(n), where n is the size of the given array.
Another Efficient Approach (Space Optimization) :
- If element should occur atleast k times after first occurrence , then their frequency in array should be atleast k+1 times .
- First we will sort the array for binary search .
- We can find frequency of arr[i] by using binary search function .
- The frequency of arr[i] will be index of ‘last occurrence – first occurrence’+1.
- So , frequency if atleast k times then increase the count by 1 .
- Then return final answer .
Below is the implementation of above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; //Function to find count of all elements that occurs //atleast k times in the array after first occurrence int countOccurrence( int arr[], int n, int k) { int count = 0; 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] int first_index = lower_bound(arr,arr+n,arr[i])- arr; int last_index = upper_bound(arr,arr+n,arr[i])- arr-1; i = last_index; // assign i to last_index to avoid counting // same element multiple time int fre = last_index-first_index+1; //finding frequency if (fre >= k+1) { // if frequency >= k+1 ,means elements occur atleast k times //then increase the count by 1 count += 1; } } return count; //return final answer } // Drive code int main() { int arr[] = { 1, 2, 1, 3 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 1; // Function call cout << countOccurrence( arr, n, k); return 0; } // This Approach is contributed by nikhilsainiofficial546 |
Java
import java.util.Arrays; public class Main { // Function to find count of all elements that occurs // atleast k times in the array after first occurrence static int countOccurrence( int [] arr, int n, int k) { int count = 0 ; Arrays.sort(arr); // sort array for binary search for ( int i = 0 ; i < n; i++) { // index of first and last occ of arr[i] int first_index = Arrays.binarySearch(arr, arr[i]); if (first_index < 0 ) { // element not found continue ; } int last_index = first_index; while (last_index + 1 < n && arr[last_index + 1 ] == arr[i]) { last_index++; } i = last_index; // assign i to last_index to avoid counting // same element multiple time int fre = last_index - first_index + 1 ; // finding frequency if (fre >= k + 1 ) { // if frequency >= k+1, means elements occur atleast k times // then increase the count by 1 count += 1 ; } } return ++count; // return final answer } // Drive code public static void main(String[] args) { int [] arr = { 1 , 2 , 1 , 3 }; int n = arr.length; int k = 1 ; // Function call System.out.println(countOccurrence(arr, n, k)); } } |
C#
using System; class MainClass { //Function to find count of all elements that occurs //atleast k times in the array after first occurrence static int countOccurrence( int [] arr, int n, int k) { int count = 0; Array.Sort(arr); //sort array for binary search for ( int i = 0; i < n; i++) { //index of first and last occ of arr[i] int first_index = Array.BinarySearch(arr, arr[i]); if (first_index < 0) { // element not found continue ; } int last_index = first_index; while (last_index + 1 < n && arr[last_index + 1] == arr[i]) { last_index++; } i = last_index; // assign i to last_index to avoid counting // same element multiple time int fre = last_index - first_index + 1; //finding frequency if (fre >= k + 1) { // if frequency >= k+1, means elements occur atleast k times // then increase the count by 1 count += 1; } } return ++count; //return final answer } //Drive code public static void Main() { int [] arr = { 1, 2, 1, 3 }; int n = arr.Length; int k = 1; //Function call Console.WriteLine(countOccurrence(arr, n, k)); } } |
Python3
# Function to find count of all elements that occur # at least k times in the array after first occurrence def countOccurrence(arr, n, k): count = 0 arr.sort() # sort array for binary search i = 0 while i < n: # index of first and last occurrence of arr[i] first_index = arr.index(arr[i]) last_index = n - arr[:: - 1 ].index(arr[i]) - 1 i = last_index # assign i to last_index to avoid counting # the same element multiple times fre = last_index - first_index + 1 # finding frequency if fre > = k + 1 : # if frequency >= k+1, means elements occur at least k times # then increase the count by 1 count + = 1 i + = 1 return count # return final answer # Drive code arr = [ 1 , 2 , 1 , 3 ] n = len (arr) k = 1 # Function call print (countOccurrence(arr, n, k)) |
Javascript
// js equivalent //Function to find count of all elements that occurs //atleast k times in the array after first occurrence function countOccurrence(arr, n, k) { let count = 0; //sort array for binary search arr.sort((a, b) => a - b); for (let i = 0; i < n; i++) { //index of first and last occ of arr[i] let first_index = arr.indexOf(arr[i]); let last_index = arr.lastIndexOf(arr[i]); i = last_index; // assign i to last_index to avoid counting // same element multiple time let fre = last_index - first_index + 1; //finding frequency if (fre >= k + 1) { // if frequency >= k+1 ,means elements occur atleast k times //then increase the count by 1 count += 1; } } return count; //return final answer } // Drive code let arr = [1, 2, 1, 3]; let n = arr.length; let k = 1; // Function call console.log(countOccurrence(arr, n, k)); |
1
Time Complexity: O(n*log2n)
Auxiliary Space: O(1)