1

I have this question that I just can't figure it out! Any hints would mean a lot. Thank you in advance. I have an array, A. It's size is n, and I want to find an algorithm that will find x that appears in this array at least n/3 times. If there is no such x in the array then we will print that we didn't find one! I need to find an algorithm that does this in O(n) time and takes O(n) space.

For example:

A=[1 1 2 2 1 1 1 5 6 7]

For the above array, the algorithm should return 1.

anna
  • 111
  • 8

2 Answers2

2

If I was you, I write an algorithm that:

  1. Instantiates a map (i.e. key/value pairs) in whatever language you're using. The key will be the integer you find, the value will be the number of times it has been seen so far.
  2. Iterate over the array. For the current integer, check whether the number exists as a key in your map. If it exists, increment the map's value. If it doesn't exist, insert a new element with a count of 1.
  3. After the iteration is complete, iterate over your map. If any elements have counts of greater than n/3, print it out. Handle the case where none are found, etc.
entpnerd
  • 10,049
  • 8
  • 47
  • 68
  • But doesn't this require O(n^2) time ?? – anna Jan 26 '20 at 04:16
  • Not at all. The iteration over the array on happens once, so that’s O(n). The iteration of the map happens once. Since the map has at most n elements (if the array contained all unique elements), the time is again O(n). Since 2*O(n) is just O(n), the time complexity is O(n). The map takes O(n) space. Since that’s the only thing using memory in your code, it’s also O(n) space. – entpnerd Jan 26 '20 at 04:25
  • but here is the problem : each integer could be very big , so the map would take a lot of space (the integers range is not from 1 to n ) – anna Jan 26 '20 at 13:15
  • so if i went to an integer in the array , i want to check if it exists in the map , and lets say this integer does exists in the map , how would i find it in O(1) ? – anna Jan 26 '20 at 13:17
  • Maps aren't usually sorted by default. They're hashed (i.e. a hash map). For example, suppose I hash my numbers and choose the hashing function ` hash(n) = n mod k`, where `k` is the number of buckets. Now I still take roughly linear space, even for big integers. – entpnerd Jan 26 '20 at 22:09
0

Here is my solution in pseudocode; note that it is possible to have two solutions as well as one or none:

func anna(A, n)                  # array and length
    ht := {}              # create empty hash table
    for k in [0,n)             # iterate over array
        if A[k] in ht             # previously seen
            ht{k} := ht{k} + 1    # increment count
        else                      # previously seen
            ht{k} := 1           # initialize count
    solved := False        # flag if solution found
    for k in keys(ht)     # iterate over hash table
        if ht{k} > n / 3           # found solution
            solved := True            # update flag
            print k                      # write it
    if not solved               # no solution found
        print "No solution"        # report failure

The first for loop takes O(n) time. The second for loop potentially takes O(n) time if all items in the array are distinct, though most often the second for loop will take much less time. The hash table takes O(n) space if all items in the array are distinct, though most often it takes much less space.

It is possible to optimize the solution so it stops early and reports failure if there are no possible solutions. To do that, keep a variable max in the first for loop, increment it every time it is exceeded by a new hash table count, and check after each element is added to the hash table if max + n - k < n / 3.

user448810
  • 17,381
  • 4
  • 34
  • 59