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

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[0]);
 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[0]);
 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

People are also reading:

• Find Subarrays within Given Sum in an Array
• Job Sequencing Problem
• Shift All Matrix Elements by 1 in Spiral Order
• Left Rotate an Array
• Delete Nodes And Return Forest
• Modular Exponentiation in Logarithmic Time
• Longest Substring without repeating characters
• Python Take list as an input from a user
• Check if directed graph is connected
• Find K-th Smallest Element in BST