## Frequency Counts

### March 8, 2019

Today we have a tricky exercise from Geeks For Geeks:

Given an unsorted array of

nintegers from 1 ton, possibly with some items appearing multiple times and others missing from the array, count the frequency of all items that are present. Your solution must run in O(n) time and take O(1) extra space.

Your task is to write a program to count frequencies as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Python

Another Python, not sure about big-O though:

Output is

1 -> 0

2 -> 2

3 -> 2

4 -> 0

5 -> 1

Below a Python solution that satisfies the O(n) time and O(1) extra space requirement. It seems I came up with the first solution given. The second solution is indeed quite neat.

Here are two solutions in C, each corresponding to one of the

Geeks for Geeksmethods.Example Output (same for both program):