Anna’s Homework

January 31, 2020

Let’s help Anna with her homework:

Given an array of n elements, find an element x that appears in the array at least n/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.

Pages: 1 2

8 Responses to “Anna’s Homework”

  1. Zack said

    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!

  2. chaw said

    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.

    (import (scheme base)
            (scheme write)
            (only (srfi 1) fold)
            (only (srfi 69)
                  make-hash-table hash-table-update!/default  hash-table-fold))
    
    (define (find-popular-items fraction items item=?)
      (let* ((ht (make-hash-table item=?))
             (n (fold (lambda (x nseen)
                        (hash-table-update!/default ht
                                                    x
                                                    (lambda (c) (+ c 1))
                                                    0)
                        (+ nseen 1))
                      0
                      items))
             (threshold (ceiling (* n fraction))))
        (hash-table-fold ht
                         (lambda (key val lst)
                           (if (>= val threshold)
                               (cons key lst)
                               lst))
                         '())))
    
    (display (find-popular-items 1/3 '(3 1 4 1 5 1 1) =))
    (newline)
    (display (find-popular-items 1/3 '(3 1 4 1 5 9 2) =))
    (newline)
    

    Output:

    (1)
    ()
    

  3. matthew said

    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.

  4. Daniel said

    Here’s a solution in Python.

    from collections import Counter
    from fractions import Fraction
    
    def anna(l):
        return [x for x, c in Counter(l).items() if c >= Fraction(len(l), 3)]
    
    print(anna([1, 1, 2, 2, 1, 1, 1, 5, 6, 7]))
    print(anna([1, 1, 1, 1, 2, 2, 2, 2, 3, 4]))
    print(anna([1, 2, 3, 4, 5]))
    

    Output:

    [1]
    [1, 2]
    []
    
  5. Daniel said

    I used Fraction to avoid floating points. Here’s a simpler solution (same output).

    from collections import Counter
    
    def anna(l):
        return [x for x, c in Counter(l).items() if c * 3 >= len(l)]
    
  6. matthew said

    Here’s that O(1) algorithm, which does seem to work, plus a test program that generates random inputs to be checked.

    import random
    
    # Given array a, length N, return n1 and n2 such that if
    # an array entry n occurs more that N/3 times, then
    # n = n1 or n = n2.
    def onethird(a):
        n1,n2,count1,count2 = 0,0,0,0
        for i, n in enumerate(a):
            #print(i,n,n1,count1,n2,count2)
            if n == n1: count1 += 1
            elif n == n2: count2 += 1
            elif count1 == 0: n1,count1 = n,1
            elif count2 == 0: n2,count2 = n,1
            else: count1 -= 1; count2 -= 1
        return n1,n2
    
    # Generate a test array for the onethird function.
    # Since we don't care when there isn't a majority
    # item, ensure that there is one, then fill in
    # the rest of the array randomly.
    def testcase(K):
        N = random.randrange(2,K+1)
        M = random.randrange(1+N//3,N+1)
        assert(3*M > N)
        a = [0]*M
        i,j = 1,M
        while j < N:
            K = random.randrange(1,N-j+1)
            a += [i]*K
            j += K
            i += 1
        assert(len(a) == N)
        for i in range(10):
            # Having constructed the array elements,
            # shuffle and test a few times.
            random.shuffle(a)
            n1,n2 = onethird(a)
            if n1 != 0 and n2 != 0:
                print(a,N,M,n1,n2)
                return
    
    for i in range(1000000): testcase(40)
    
  7. Steve said

    Klong version

            l
    Code:
            {[a a2];a::x;{a@*x}'a2@&{2<#x}'a2::=a}'[[1 1 2 2 1 1 1 5 6 7] [1 1 1 1 2 2 2 2 3 4] [1 2 3 4 5]];""
    [[1] [1 2] []]
    ""
    
    Explanation:
            l :"list"
    [1 2 3 3 4 5 6 7 3 2 2 2]
            =l :"find locations of unique members of list"
    [[0] [1 9 10 11] [2 3 8] [4] [5] [6] [7]]
            {2<#x}'a2::=l :"find if those member which occur >2 times = winners"
    [0 1 1 0 0 0 0]
            &{2<#x}'a2::=l :"narrow it down to only the positions of the winners"
    [1 2]
            a2@&{2<#x}'a2::=l :"get the positions of the winners"
    [[1 9 10 11] [2 3 8]]
            {a@*x}'a2@&{2<#x}'a2::=l :"get the numbers"
    [2 3]
    
  8. Steve said

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

            {[a a2 n];a::x;n::(#a)%3;{a@*x}'a2@&{~n>#x}'a2::=a}'[[1 1 2 2 1 1 1 5 6 7] [1 1 1 1 2 2 2 2 3 4] [1 2 3 4 5]]
    [[1] [1 2] []]
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: