# Would anybody mind explaining this Divide and Conquer to me ? What is really going on here ? Thanks

• This method was proposed by someone to find majority element in the array.I can't really understand how things are going on.Can anyone explain this to me.

Regards.

• Let f(i, j) be the majority of elements from i-th to j-th in nums

By the definition of majority it is the number of elements that appears more than half of the total numbers in the array,

• f(i, mid) appears more than (mid - i+1)/2 times from i-th to mid-th in nums
• f(mid+1, j) appears more than (j - mid)/2 times from (mid+1)-th to j-th in nums

Assume that all the rest elements in nums from i-th to j-th except those two numbers above are the same,
then they will appear less than (mid-i+1)/2 + (j-mid)/2 = (j-i+1)/2 times from i-th to j-th in nums

Therefore any elements except those two numbers above cannot be the majority of elements in nums;
hence f(i,j) = f(i,mid) or f(mid+1,j)

• Then what's next? how to make the decision between f(i,mid) and f(mid+1,j)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.