## Frequency Counts

### March 8, 2019

Today we have a tricky exercise from Geeks For Geeks:

Given an unsorted array of n integers from 1 to n, 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.

Pages: 1 2

### 5 Responses to “Frequency Counts”

1. Milbrae said

Python

```def freqcount(seq):
c =  * (len(seq))
for i in seq:
c[i-1] += 1
return c

if __name__ == "__main__":
data = [2, 3, 3, 2, 5]
fc = freqcount(data)
for i in range(len(data)):
print ("%d -> %d" % (i+1, fc[i]))
```
2. Milbrae said

Another Python, not sure about big-O though:

```from collections import Counter

if __name__ == "__main__":
data = [2, 3, 3, 2, 5]
fc = Counter(data)
for i in range(len(data)):
print ("%d -> %d" % (i+1, fc.get(i+1, 0)))
```

Output is
1 -> 0
2 -> 2
3 -> 2
4 -> 0
5 -> 1

3. Jan Van lent said

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.

```import random

n = 8
a = [ random.randrange(n)+1 for i in range(n) ]
print(a)
# frequency count for checking purposes
# this requires O(n) storage, so this is not a valid answer
c = *n
for i in range(n):
c[a[i]-1] += 1
print(c)

# move through the array
# turn each entry a[i] into the negative of the count for the number i+1
# in each step we either move to the next entry and/or increase the number
# of entries that have become counts rather than numbers to be counted
i = 0
while i < n:
if a[i] <= 0: # already a count, move on
i = i + 1
else: # number to be counted
if a[i]-1 == i: # number is the position of its count
a[i] = -1
elif a[a[i]-1] > 0:
# there is a number in the place where a[i]'s count should go
# swap number to current place, update count and don't move on
tmp = a[a[i]-1]
a[a[i]-1] = -1
a[i] = tmp
else: # the entry for a[i] is already a count, update count, make current entry count and move on
a[a[i]-1] -= 1
a[i] = 0
i = i + 1
for i in range(n):
a[i] = -a[i]
print(a)
print(a==c)
```
4. Steve said
```
Klong version

:" \$x - Change number to string; ?l - Returns unique elements in list l; l?x - Returns position(s) of element x in list l; #l?x - Returns count of positions of element x in list l; \$#l?x - Returns string equivalent of count of positions of element x in list l"

Code:
freqcnts::{[l]; l::x; {.p((\$x),": ",\$#l?x)}'?l; :done}

Run:
freqcnts([2 3 3 2 5])
2: 2
3: 2
5: 1
:done
freqcnts([9 8 9 7 7 5 6])
9: 2
8: 1
7: 2
5: 1
6: 1
:done

```
5. Daniel said

Here are two solutions in C, each corresponding to one of the Geeks for Geeks methods.

```#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[]) {
int n  = argc - 1;
int* array = malloc(n * sizeof(int));
for (int i = 0; i < n; ++i) {
array[i] = atoi(argv[i + 1]);
}
int i = 0;
while (i < n) {
int x = array[i];
if (x < 0) {
++i;
continue;
}
if (array[x - 1] > 0) {
array[i] = array[x - 1];
array[x - 1] = -1;
continue;
}
--array[x - 1];
++i;
}
for (int i = 0; i < n; ++i) {
int count = array[i] < 0 ? -array[i] : 0;
printf("%d: %d\n", i + 1, count);
}
free(array);
return EXIT_SUCCESS;
}
```
```int main(int argc, char* argv[]) {
int n  = argc - 1;
int* array = malloc(n * sizeof(int));
for (int i = 0; i < n; ++i) {
array[i] = atoi(argv[i+1]) - 1;
}
for (int i = 0; i < n; ++i) {
array[array[i] % n] += n;
}
for (int i = 0; i < n; ++i) {
printf("%d: %d\n", i + 1, array[i] / n);
}
free(array);
return EXIT_SUCCESS;
}
```

Example Output (same for both program):

```\$ ./a.out 1 3 5 7 9 1 3 5 7 9 1
1: 3
2: 0
3: 2
4: 0
5: 2
6: 0
7: 2
8: 0
9: 2
10: 0
11: 0
```