Search code examples
carraysalgorithmdivide-and-conquer

Most Element in Array Divide-And-Conquer O(N.log(N))


An array a [], with N elements, admitting repeated, is said to "contain a v element mostly" if more than half of its content equals v. Given the array a [], it is intended to draw an efficient algorithm (at time N.log (N) and using divide-and-conquer) to check if it contains a majority element and to determine it. Consider the only available comparison operation between elements of the array, is the equality (a [i] == a [j]), performed in constant time. (Hint: In the algorithm, divide the array to [] into two subarrays a1 [] and a2 [], each one half the size of a []. If the element in most of a [] is v, then v must be also the element in majority of a1 [], or a2 [] or both).

int main() {

    int a[12] = {5, 9, 3, 13, 5, 21, 5, 7, 17, 12, 5, 6};
    int N = 12, lo = 0, hi = N - 1, mid,i,j;

    mid = lo + (hi - lo) / 2;
    int n1 = mid - lo + 1;
    int n2 =  hi - mid;
    int a1[n1],a2[n2];

    /* Copy data to temp arrays a1[] and a2[] */
    for (i = 0; i < n1; i++)
        a1[i] = a[lo + i];
    for (j = 0; j < n2; j++)
        a2[j] = a[mid+1+j];


    while (i < n1 && j < n2) {

        if(a1[i]==a2[j]){

        }else if(){


        }else{


        }

    }
    return 0;
}

Im having troubles on the way I should proceed using the operation of equality comparing the auxiliar arrays to see if the most element is on a1[] or a2[] or both!


Solution

  • Here's a Python implementation that fits the description (sorry, I'm not versed in C but I think it's pretty straightforward code). We can follow the logged return values and indexes for each section that's examined to make sense of how it works.

    # Returns v if v is a majority;
    # otherwise, returns None
    def f(arr, low, high):
      if low == high:
        return arr[low]
    
      if low + 1 == high:
        return arr[low] if arr[low] == arr[high] else None
    
      n = high - low + 1
      mid = (low + high) / 2
    
      l = f(arr, low, mid)
      r = f(arr, mid + 1, high)
    
      print 'n: ' + str(n) + '; l: ' + str(l) + '; r: ' + str(r) + '; L: ' + str((low, mid)) + '; R: ' + str((mid + 1, high))
    
      if l == r:
        return l
    
      counts = [0, 0]
    
      for i in xrange(low, high + 1):
        if arr[i] == l:
          counts[0] = counts[0] + 1
        if arr[i] == r:
          counts[1] = counts[1] + 1
    
      if l and counts[0] * 2 > n:
        return l
    
      if r and counts[1] * 2 > n:
        return r
    
      return None
    

    Output:

    a = [5, 9, 3, 5, 5, 21, 5, 7, 17, 5, 5, 5]
    
    print f(a, 0, len(a) - 1)
    
    """
    n: 3; l: None; r: 3; L: (0, 1); R: (2, 2)
    n: 3; l: 5; r: 21; L: (3, 4); R: (5, 5)
    n: 6; l: None; r: 5; L: (0, 2); R: (3, 5)
    n: 3; l: None; r: 17; L: (6, 7); R: (8, 8)
    n: 3; l: 5; r: 5; L: (9, 10); R: (11, 11)
    n: 6; l: None; r: 5; L: (6, 8); R: (9, 11)
    n: 12; l: None; r: 5; L: (0, 5); R: (6, 11)
    5
    """