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

Posted in

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

Maaz Bin Asad
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[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:

    Leave a Comment on this Post

    0 Comments