Given an array arr[], the task is to find the number of times the current integer has already occurred during array traversal.
Examples:
Input: arr[] = {2, 3, 3, 200, 175, 2, 200, 2, 175, 3}
Output: 0 0 1 0 0 1 1 2 1 2
Explanation: Before the 0th index, 2 is encountered 0 times. Before the 2nd index, 3 is encountered once at index 1. Similarly, before the 7th index, 2 is occurred twice and so on.Input: arr[] = {200, 200, 55, 200, 55, 2, 3, 2}
Output: 0 1 0 2 1 0 0 1
Naive Approach:
The naive approach to solve the problem is to run two nested loops: one to traverse each element of the array and another to traverse from 0 to the i-1 element to check how many times ith element has occurred already.
Algorithm:
1. Create a function that takes an array and its length as input.
2. Traverse the array from 0 to n-1:
a. Initialize a variable count to 0.
b. Traverse the array from 0 to i-1:
i. If the current element matches a previous element, increment count.
c. Print the count for the current element.
Below is the implementation of the approach:
C++
// C++ code for the approach#include<bits/stdc++.h> using namespace std;// function to find the number of times // an integer has already occurredvoid countOccurences(int arr[], int n) { for(int i=0; i<n; i++) { // initialize count to 0 int count = 0; for(int j=0; j<i; j++) { // if current element matches a previous element if(arr[i] == arr[j]) { // increment count count++; } } // print count for current element cout << count << " "; }}// Driver's codeint main() { int arr[] = { 2, 3, 3, 200, 175, 2, 200, 2, 175, 3 }; int n = sizeof(arr)/sizeof(arr[0]); // Function call countOccurences(arr, n); return 0;} |
Java
import java.util.Arrays;public class GFG { // Function to find the number of times an integer has already occurred public static void countOccurrences(int[] arr, int n) { for (int i = 0; i < n; i++) { // Initialize count to 0 int count = 0; for (int j = 0; j < i; j++) { // If the current element matches a previous element if (arr[i] == arr[j]) { // Increment count count++; } } // Print count for the current element System.out.print(count + " "); } } // Driver's code public static void main(String[] args) { int[] arr = { 2, 3, 3, 200, 175, 2, 200, 2, 175, 3 }; int n = arr.length; // Function call countOccurrences(arr, n); }} |
Python3
# Function to find the number of times an integer has already occurreddef count_occurrences(arr): for i in range(len(arr)): # Initialize count to 0 count = 0 for j in range(i): # If the current element matches a previous element if arr[i] == arr[j]: # Increment count count += 1 # Print count for the current element print(count, end=" ")# Driver's codeif __name__ == "__main__": arr = [2, 3, 3, 200, 175, 2, 200, 2, 175, 3] # Function call count_occurrences(arr) |
C#
using System;class Program{ // Function to find the number of times // an integer has already occurred static void CountOccurrences(int[] arr, int n) { for (int i = 0; i < n; i++) { // Initialize count to 0 int count = 0; for (int j = 0; j < i; j++) { // If current element matches a previous element if (arr[i] == arr[j]) { // Increment count count++; } } // Print count for current element Console.Write(count + " "); } } // Main method static void Main() { int[] arr = { 2, 3, 3, 200, 175, 2, 200, 2, 175, 3 }; int n = arr.Length; // Function call CountOccurrences(arr, n); }} |
Javascript
function countOccurrences(arr) { const n = arr.length; for (let i = 0; i < n; i++) { // Initialize count to 0 let count = 0; for (let j = 0; j < i; j++) { // If the current element matches a previous element if (arr[i] === arr[j]) { // Increment count count++; } } // Print count for the current element console.log(count + ' '); }}// Driver's codefunction main() { const arr = [2, 3, 3, 200, 175, 2, 200, 2, 175, 3]; // Function call countOccurrences(arr);}main(); |
Output
0 0 1 0 0 1 1 2 1 2
Time Complexity: O(N*N) as two nested loops are executing. Here, N is size of input array.
Space Complexity: O(1) as no extra space has been used.
Approach: The task can be solved by keeping track of frequencies of distinct elements till the current element using a HashMap. Follow the below steps to solve the problem:
- Create a hashmap say ‘occ‘, to store the frequencies of the distinct elements till the current element
- For the current element, check whether it already exists inside the hashmap or not.
- If it exists, store the frequency corresponding to it, else store 0.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the number of// times current integer has already// occurred during array traversal.void getOccurrences(vector<int>& arr){ // Store the size of array int n = arr.size(); // Hashmap to keep track of // the frequencies unordered_map<int, int> occ; for (int i = 0; i < n; ++i) { // If element is already // present inside hashmap if (occ.find(arr[i]) != occ.end()) { cout << occ[arr[i]] << " "; } else { cout << 0 << " "; } // Increment the frequency occ[arr[i]]++; }}// Driver Codeint main(){ vector<int> arr = { 2, 3, 3, 200, 175, 2, 200, 2, 175, 3 }; getOccurrences(arr); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to find the number of // times current integer has already // occurred during array traversal. static void getOccurrences(int[] arr) { // Store the size of array int n = arr.length; // Hashmap to keep track of // the frequencies HashMap<Integer, Integer> occ = new HashMap<Integer, Integer>(); for (int i = 0; i < n; ++i) { // If element is already // present inside hashmap if (occ.containsKey(arr[i])) { System.out.print(occ.get(arr[i]) + " "); // Increment the frequency occ.put(arr[i], occ.get(arr[i]) + 1); } else { System.out.print(0 + " "); // Increment the frequency occ.put(arr[i], 1); } } } // Driver Code public static void main(String[] args) { int[] arr = { 2, 3, 3, 200, 175, 2, 200, 2, 175, 3 }; getOccurrences(arr); }}// This code is contributed by ukasp. |
Python3
# python3 program for the above approach# Function to find the number of# times current integer has already# occurred during array traversal.def getOccurrences(arr): # Store the size of array n = len(arr) # Hashmap to keep track of # the frequencies occ = {} for i in range(0, n): # If element is already # present inside hashmap if (arr[i] in occ): print(occ[arr[i]], end=" ") else: print(0, end=" ") # Increment the frequency occ[arr[i]] = occ[arr[i]] + 1 if arr[i] in occ else 1# Driver Codeif __name__ == "__main__": arr = [2, 3, 3, 200, 175, 2, 200, 2, 175, 3] getOccurrences(arr)# This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to find the number of // times current integer has already // occurred during array traversal. static void getOccurrences(int []arr) { // Store the size of array int n = arr.Length; // Hashmap to keep track of // the frequencies Dictionary<int, int> occ = new Dictionary<int, int>();; for (int i = 0; i < n; ++i) { // If element is already // present inside hashmap if (occ.ContainsKey(arr[i])) { Console.Write(occ[arr[i]] + " "); // Increment the frequency occ[arr[i]] = occ[arr[i]] + 1; } else { Console.Write(0 + " "); // Increment the frequency occ.Add(arr[i], 1); } } } // Driver Code public static void Main() { int []arr = { 2, 3, 3, 200, 175, 2, 200, 2, 175, 3 }; getOccurrences(arr); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find the number of // times current integer has already // occurred during array traversal. function getOccurrences(arr) { // Store the size of array let n = arr.length; // Hashmap to keep track of // the frequencies let occ = new Map(); for (let i = 0; i < n; ++i) { // If element is already // present inside hashmap if (occ.has(arr[i])) { document.write(occ.get(arr[i]) + " "); } else { document.write(0 + " "); } // Increment the frequency if (occ.has(arr[i])) occ.set(arr[i], occ.get(arr[i]) + 1); else occ.set(arr[i], 1); } } // Driver Code let arr = [2, 3, 3, 200, 175, 2, 200, 2, 175, 3]; getOccurrences(arr); // This code is contributed by Potta Lokesh </script> |
Output
0 0 1 0 0 1 1 2 1 2
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
