## Frequency Counts

### March 8, 2019

Geeks For Geeks gives two solutions. The first one scans the array, accumulating the negative of the count at the index location of the array item, changing seen items to zero:

(define (freq vec) (let ((n (vector-length vec))) (let loop ((i 0)) (cond ((= i n) (do ((j 0 (+ j 1))) ((= j n)) (when (negative? (vector-ref vec j)) (display (+ j 1)) (display " ") (display (- (vector-ref vec j))) (newline)))) ((not (positive? (vector-ref vec i))) (loop (+ i 1))) (else (let ((idx (- (vector-ref vec i) 1))) (cond ((positive? (vector-ref vec idx)) (vector-set! vec i (vector-ref vec idx)) (vector-set! vec idx -1) (loop i)) (else (vector-set! vec idx (- (vector-ref vec idx) 1)) (vector-set! vec i 0) (loop (+ i 1))))))))))

> (freq '#(2 3 3 2 5)) 2 2 3 2 5 1

That works, but the logic is tricky (quickly: explain why one branch of the inner `cond`

calls `(loop i)`

while the other branch calls `(loop (+ i 1))`

), and it destroys the contents of the array; it is possible to recreate the contents of the array, but not their original order. Here is the second solution:

(define (freq vec) (let ((n (vector-length vec))) (do ((i 0 (+ i 1))) ((= i n)) (vector-set! vec i (- (vector-ref vec i) 1))) (do ((i 0 (+ i 1))) ((= i n)) (vector-set! vec (modulo (vector-ref vec i) n) (+ (vector-ref vec (modulo (vector-ref vec i) n)) n))) (do ((i 0 (+ i 1))) ((= i n)) (when (< n (vector-ref vec i)) (display (+ i 1)) (display " ") (display (quotient (vector-ref vec i) n)) (newline))) (do ((i 0 (+ i 1))) ((= i n)) (vector-set! vec i (+ (remainder (vector-ref vec i) n) 1))) (display vec) (newline))) ; show that vec is unchanged

> (freq '#(2 3 3 2 5)) 2 2 3 2 5 1 #(2 3 3 2 5)

After redefining the data from 1â*n* to 0â*n*â1, this adds *n* at the index of each item in the array, so you can calculate the count and the original item in the array as the quotient and remainder on dividing by *n*. Very clever!

You can run the program at https://ideone.com/nm6KzX.

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.