C++ Solution using Divide and Conquer, Time Complexity: O(log n) [CORRECT ME IF I AM WRONG]

Tags: #<Tag:0x00007f1828ed75a0>

#1

The question asks us to perform a minimum number of comparisons to get a maximum and minimum element from the array so doing comparison linearly will result in O(n) time complexity, hence a divide and conquer approach is required.

``````pair<int, int> getMaxMin(vector<int> &A, int start, int last){

int n = last - start + 1 ;
if(n <= 2){
int maxEle = max(A[start], A[last]) ;
int minEle = min(A[start], A[last]) ;
return make_pair(maxEle, minEle) ;
}

int mid = (int)(start + last)/2 ;
pair<int, int> left = getMaxMin(A, start, mid) ;
pair<int, int> right = getMaxMin(A, mid+1, last) ;

int maxEle = max(left.first, right.first) ;
int minEle = min(left.second, right.second) ;

return make_pair(maxEle, minEle) ;
}

int Solution::solve(vector<int> &A) {

if(A.size() == 1){
return A[0] + A[0] ;
}

pair<int, int> maxMinEle = getMaxMin(A, 0, A.size()-1) ;

return maxMinEle.first + maxMinEle.second ;
}
``````

Any improvements int the code is welcomed.

#2

I think it is still O(n) complexity. You are not making a choice to go either left or right. You are going both ways, and accessing all the elements in the array.

#3

Hi, thanks for the reply, has the number of comparisons reduced by log N instead of N if we had used the linear method?

#4

Normally we do this nX1
you are doing n(1/2 +1/2)
same things bro.