## Anna’s Homework

### January 31, 2020

Let’s help Anna with her homework:

Given an array of

nelements, find an elementxthat appears in the array at leastn/3 times, or indicate that no such element exists. Your program may take no more than O(n) time and O(n) space.

Your task is to write a program to solve Anna’s homework problem. 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.

Here is my take on this in Julia: https://pastebin.com/xv0xnX5d

I’m not sure if the code is optimal, but I’m open to suggestions on how to improve it.

Have a nice weekend!

Here is a simple solution in R7RS Scheme plus a few helpers from

popular SRFIs. The algorithm is the same as the one by

@programmingpraxis, but the implementation is a bit more general

(although it should probably include a item-hash argument too) and

tries to use built-in procedures as much as possible. It is O(n) with

the usual caveat about hash tables.

Output:

I haven’t checked it, but https://stackoverflow.com/questions/14955634/number-which-appears-more-than-n-3-times-in-an-array has an algorithm that claims to be O(1) space – it’s a variant on the Boyer-Moore majority voting algorithm that is definitely OK.

Here’s a solution in Python.

Output:

I used

`Fraction`

to avoid floating points. Here’s a simpler solution (same output).Here’s that O(1) algorithm, which does seem to work, plus a test program that generates random inputs to be checked.

Klong version

Klong version #2 – Need to measure number of matches to length of list, and not an arbitrary number