Given an array of positive integers with duplicate allowed. The array contains elements from range 0 to n-1. The task is to fill the array such that arr[i] contains the frequency of i.
Examples :
Input : arr[] = {1, 4, 3, 4, 1, 1, 4, 4, 4, 7}
Output : arr[] = {0, 3, 0, 1, 5, 0, 0, 1, 0, 0}
Here 0 appears 0 times, so arr[0] is 0
1 appears 3 times
2 appears 0 times
3 appears 0 times
4 appears 5 times
..........
Input : arr[] = {1, 2, 3, 4, 1, 1, 4, 5, 6, 7}
Output : arr[] = {0, 3, 1, 1, 2, 1, 1, 1, 0, 0}
A simple solution of this problem is to run two loops. The outer loop picks elements one by one. The inner loop counts frequency of the picked element and stores frequency in final array.
An efficient solution is to use an auxiliary array of size n.
1) Create an array temp[0..n-1] and
initialize it as 0.
2) Traverse given array and do following
for every element arr[i].
temp[arr[i]]++
3) Copy temp[] to arr[].
Below is the implementation of above steps.
C++
// C++ program to fill an array with frequencies. #include<bits/stdc++.h> using namespace std; // Fills arr[] with frequencies of elements void fillWithFreq(int arr[], int n) { int temp[n]; memset(temp, 0, sizeof(temp)); // Fill temp with frequencies for (int i=0; i<n; i++) temp[arr[i]] += 1; // Copy temp to array for (int i=0; i<n; i++) arr[i] = temp[i]; } // Driver code int main() { int arr[] = {5, 2, 3, 4, 5, 5, 4, 5, 6, 7}; int n = sizeof(arr)/sizeof(arr[0]); fillWithFreq(arr, n); for (int i=0; i<n; i++) cout << arr[i] << " "; return 0; } |
Java
// Java program to fill an array with frequencies. import java.util.Arrays; class GFG { // Fills arr[] with frequencies of elements static void fillWithFreq(int arr[], int n) { int temp[]=new int[n]; Arrays.fill(temp, 0); // Fill temp with frequencies for (int i = 0; i < n; i++) temp[arr[i]] += 1; // Copy temp to array for (int i = 0; i < n; i++) arr[i] = temp[i]; } // Driver method public static void main(String[] args) { int arr[] = {5, 2, 3, 4, 5, 5, 4, 5, 6, 7}; int n = arr.length; fillWithFreq(arr, n); for (int i=0; i<n; i++) System.out.print(arr[i] + " "); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 program to fill an # array with frequencies. # Fills arr[] with frequencies of elements def fillWithFreq(arr, n): temp = [0 for i in range(n)] # Fill temp with frequencies for i in range(n): temp[arr[i]] += 1 # Copy temp to array for i in range(n): arr[i] = temp[i] # Driver Code arr = [5, 2, 3, 4, 5, 5, 4, 5, 6, 7] n = len(arr) fillWithFreq(arr, n) for i in range(n): print(arr[i], end = " ") # This code is contributed by Anant Agarwal. |
C#
// C# program to fill an // array with frequencies. using System; class GFG { // Fills arr[] with frequencies of elements static void fillWithFreq(int []arr, int n) { int []temp = new int[n]; for(int i = 0; i < n; i++) temp[i] = 0; // Fill temp with frequencies for (int i = 0; i < n; i++) temp[arr[i]] += 1; // Copy temp to array for (int i = 0; i < n; i++) arr[i] = temp[i]; } // Driver method public static void Main() { int []arr = {5, 2, 3, 4, 5, 5, 4, 5, 6, 7}; int n = arr.Length; // Function calling fillWithFreq(arr, n); for (int i = 0; i < n; i++) Console.Write(arr[i] + " "); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP program to fill an // array with frequencies. // Fills arr[] with frequencies // of elements function fillWithFreq($arr, $n) { $temp = array(); for($i = 0; $i < $n; $i++) $temp[$i] = 0; // Fill temp with frequencies for ($i = 0; $i < $n; $i++) $temp[$arr[$i]] += 1; // Copy temp to array for ($i = 0; $i < $n; $i++) $arr[$i] = $temp[$i]; // print array for ($i = 0; $i < $n; $i++) echo $arr[$i] . " "; } // Driver method $arr = array(5, 2, 3, 4, 5, 5, 4, 5, 6, 7); $n = count($arr); // Function calling fillWithFreq($arr, $n); // This code is contributed by Sam007 ?> |
Javascript
<script> // Javascript program to fill an // array with frequencies. // Fills arr[] with frequencies of elements function fillWithFreq(arr, n) { let temp = new Array(n); for(let i = 0; i < n; i++) temp[i] = 0; // Fill temp with frequencies for (let i = 0; i < n; i++) temp[arr[i]] += 1; // Copy temp to array for (let i = 0; i < n; i++) arr[i] = temp[i]; } let arr = [5, 2, 3, 4, 5, 5, 4, 5, 6, 7]; let n = arr.length; // Function calling fillWithFreq(arr, n); for (let i = 0; i < n; i++) document.write(arr[i] + " "); </script> |
Output
0 0 1 1 2 4 1 1 0 0
Time Complexity : O(n)
Auxiliary Space : O(n)
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
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!
