# Efficiently calculate the frequency of all elements present in a limited range array

Posted in  Last updated on November 30, 2023

## Problem

Given an array of the sizes ``` n ``` where elements range from ``` 0 to ``` ``` n-1 ``` . Calculate the frequency of each element in constant space.

#### Sample Input

`[1, 2, 2, 3]`

#### Sample Output

```1: 1
2: 2
3: 1```

### Approach

Since the elements lie in the range 0 to n-1, we can increment elements present at the index ``` a[i]%n ``` by ``` n ``` . After this step, we can traverse through the modified array and see if some element appears more than or equal to ``` n ``` times. If we find this, the element ``` i ``` appears ``` a[i]/n ``` times.

#### C

```#include <stdio.h>
voidsolve(int arr[], int n)
{
for (int i = 0; i < n; i++) {
arr[arr[i] % n] += n;
}
for (int i = 0; i < n; i++)
{
if (arr[i]/n != 0) {
printf("%d: %d\n", i, arr[i]/n);
}
}
for (int i = 0; i < n; i++) {
arr[i] = arr[i] % n;
}
}
intmain(void)
{
int arr[] = {1, 2, 2, 3 };
int n = sizeof(arr) / sizeof(arr);
solve(arr, n);
return0;
}```

#### Output

```1: 1
2: 2
3: 1```

#### C++

```#include <bits/stdc++.h>
usingnamespacestd;
voidsolve(int arr[], int n)
{
for (int i = 0; i < n; i++) {
arr[arr[i] % n] += n;
}
for (int i = 0; i < n; i++)
{
if (arr[i]/n != 0) {
cout<<i<<": "<<arr[i]/n<<"\n";
}
}
for (int i = 0; i < n; i++) {
arr[i] = arr[i] % n;
}
}
intmain(void)
{
int arr[] = {1, 2, 2, 3 };
int n = sizeof(arr) / sizeof(arr);
solve(arr, n);
return0;
}```

#### Output

```1: 1
2: 2
3: 1```

#### Python

```def solve(arr):
n = len(arr)
for i in range(n):
arr[arr[i] % n] += n
for i in range(n):
if arr[i] // n:
print(f"{i}: {arr[i] // n}")
for i in range(n):
arr[i] = arr[i] % n
arr = [1, 2, 2, 3]
solve(arr)```

#### Output

```1: 1
2: 2
3: 1```