in Algorithms
1,286 views
3 votes
3 votes
Leading element in an array of n elements is the element which occurs more than n/2 times in the array.

a) What is the time complexity to find whether a leading element exists or not in a sorted array of n elements?

b)What is the time complexity to find whether a leading element exists or not in an array whose range of values are between 0 to n?

c)What is the time complexity to find whether leading element exists or not in an unsorted array of n elements?
in Algorithms
1.3k views

4 Comments

Just have to look once in the middle item that's all.In a sorted array it must be in the middle by given condition that it must occur n/2 times of the array,hence O(1). Why to look other indices?
0
0
what are you trying to say ???
0
0
IN SORTED ARRAYS

He's saying that .. If the leading element X which occurs n/2 times.

Then it should be there at the position n/2.

Position : 1 2 3 4 5 6 7.... n/2 ..... n

Element : n/2 times So, from (1 to n/2) or (2 to n/2 +1) or (n/2 to n) ..

If we check the middle element we can easily find out ...
0
0

1 Answer

1 vote
1 vote

What is the time complexity to find whether leading element exists or not in an unsorted array of n elements?

First we find the majority Element in an array :

I:e

Array :  3  5  3  3  5 3  3  7 3  5

n = 10

int count = 0 ;

int candidate  = 0

     

Integer candidate = null;
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (count == 0) {
                candidate = array[i];
                count = 1;
                continue;
            } else {
                if (candidate == array[i]) {
                    count++;
                } else {
                    count--;
                }
            }
        }
 
 
Explanation :
Iteration 1    : array[0] = 3 ,     candidate = 3    , count = 1 ;
Iteration 2    : array[1] = 5 ,     count - -  , count = 0 , candidate = 3
Iteration 3    : array[2] = 3 ,     candidate = 3 ,  count  = 1
iteration 4    : array[3] = 3 ,     candidate == array[3] // holds true , count++  , count = 2 ,  candidate = 3
iteration 5    : array[4] =  5,     count - - , count = 1 , candidate = 3
iteration 6    : array[5] = 3 ,     candidate == array[5] // holds true , count ++ , count  = 2 , candidate = 3
iteration 7    : array[6] = 3 ,     candidate == array[6] // holds true , count ++ , count = 3 , candidate = 3
iteration 8    : array[7] = 7 ,     count - - , count = 2 ,  candidate = 3
iteration 9    : array[8] = 3 ,     candidate == array[8] // hold true ,  count ++ , count = 3
Iteration 10 : array[9] = 5 ,      count- - ,  count = 2 , candidate = 3
 
we done out execution in which final count = 2 and candidate =  3
which mean candidate = 3  is our majority element which occurs most of the  time
and this required : O(n)
 
Now , we have to check whether it occurs greater then n/2 times or not
 
count = 0;
        for (int i = 0; i < array.length; i++) {
            if (candidate == array[i]) {
                count++;
            }
        }
        return (count > array.length / 2) ? candidate : null;
    }

  it also required : O(n)

 

total time complexity : O(n) + O(n) = O(n)

 

by