5

I am working on my algorithm solving skills, and I am having trouble solving this problen in O(1) memory complexity.

Problem statement:

Given an array of integer numbers your task is to print to the standard output (stdout) the majority number. One number is considered majority if it occurs more than N / 2 times in an array of size N. Note: If no number is majority then print "None" Expected complexity: O(N) time, O(1) memory

Example input:

1 1 2 3 4 1 6 1 7 1 1

Example output:

1

Example input:

1 2 2 3

Example output:

None

Here is my code. I believe this is O(n) time (please correct me if I'm wrong), but this does not seem like O(1) memory. How can I achieve O(n) time and O(1) memory?

def majority(v):
    nums={}
    for num in v:
        if num in nums:
            nums[num]+=1
        else: nums[num]=1
    maxcount=['None',0]
    for num in nums:
        if nums[num] > maxcount[1] and nums[num] > len(v)/2: 
            maxcount[0] = num
            maxcount[1]=nums[num]
    print maxcount[0]
kilojoules
  • 9,768
  • 18
  • 77
  • 149
  • 1
    Are you sure the requirement is not `O(k)` memory? For a fixed/constant `k` - such as the digits 1..9 - this would allow it to be claimed as `O(1)`. (See a [counting sort](http://en.wikipedia.org/wiki/Counting_sort) for n vs k.) – user2864740 Dec 26 '14 at 03:24
  • I believe that is acceptable. What I need is for the memory required to not scale with the input data. – kilojoules Dec 26 '14 at 03:27
  • 1
    k != n. If the input is *only* the digits 1-9 then it's a constant bound -> O(1). If the problem allows for "any integer" in the input (ie. k is not constant) then I do not believe it is possible to get O(1). – user2864740 Dec 26 '14 at 03:29
  • I think I understand. Basically, my solutions's required memory only scales with the range of data supplied. Thank you for the insightful answer. – kilojoules Dec 26 '14 at 03:31
  • 4
    There is [Moore's Linear Time Majority Vote Algorithm](http://www.cs.utexas.edu/~moore/best-ideas/mjrty/). I believe it is O(1) in space. – jfs Dec 26 '14 at 03:32
  • 1
    (Definitely read the [link](http://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.html) in the above link. Seems too simple. Doh.) – user2864740 Dec 26 '14 at 03:36
  • Part of the problem is that the number of occurrences must be > n/2 to be considered majority. It doesn't seem like the Moore's algorithm will recognize this... – kilojoules Dec 26 '14 at 03:52
  • 1
    @kilojoules: Just pass the input the 2nd time and count how many times the found element occures if it is `> n/2` then you found the majority element otherwise `print("None")` – jfs Dec 26 '14 at 03:58

1 Answers1

8

Here's Python implementation of the linear time constant space majority vote algorithm:

def majority_element(seq, default=None):
    """Find which element in *seq* sequence is in the majority.

    Return *default* if no such element exists.

    Use Moore's linear time constant space majority vote algorithm
    """
    candidate = default
    count = 0
    for e in seq:
        if count != 0:
            count += 1 if candidate == e else -1
        else: # count == 0
            candidate = e
            count = 1

    # check the majority
    return candidate if seq.count(candidate) > len(seq) // 2 else default

Example

print(majority_element("A A A C C B B C C C B C C".split()))
print(majority_element("A A A A C B C C C B C C".split()))

Output

C
None

There is no majority in the second case.

jfs
  • 399,953
  • 195
  • 994
  • 1,670