Find the largest possible value for all pairs (i,j) of the array , x = a[i] + a[j] , with a constraint such that x<=m ?

Question

Expected Time Complexity : O(N*log(N)) , where 'N'  is the size of array .

1<=A[i]<=1000000

1<=N<=100000

Example :

100 200 400 10000 5 5 300

M = 650

Output : 500 ( 200 + 400 is the maximum possible value which is less than 650) .

Note :

1)Algorithm-explanation is must .

2)Adding code is optional .

3)Use Format option while adding code

Answer 1

Solution  :

1)Sort the given array .

2)Traverse the array , say you are at index 'i' , observe a[i] , we want to find a[j], such that a[i] + a[j] < = m ,

which means : a[j]<=m-a[i].

3)Let y = m - a[i] . Binary search 'y' in rage [1,i-1] of array 'a' . So you found out value of a[i] + a[j] < = m , do this for all indices 'i' and output the maximum of all of them  .

Answer 2

100 200 400 10000 5 5 300

After sorting O(nlogn)

5 5 100 200 300 400 1000      diff       sum

l                                    r        355      1005

    l                        r                 245       405

         l                    r                 245       405

               l              r                 50        600

                      l     r                   50         700   but exceeds the value of M so max sum will be 600..

              

 

If curr_right > 650 || sum>650 -> so we need to move right pointer to left

Else we need to move the left pointer to the right

 

O(n)

int solution(int arr[], int size, int M){

    // Initializing the left and right pointers

    int left = 0;

    int right = size-1;

    sort(arr, arr+size);

    int near_sum;

    int sum;

    int min_diff  = abs(arr[left]+arr[right] - M);

    while(left<right){

        int curr_sum = arr[left] + arr[right];

        int diff = abs(M-curr_sum);

        if(arr[left] > M || curr_sum > M) right--;

        else left++;

        if(diff<min_diff && curr_sum<=M) near_sum = curr_sum;

    }

    return near_sum;

}

Total Time complexity O(nlogn)+O(n) => O(nlogn)

Answer 3

Sort the array , then search position of M in array and then sum previous two elements from that position .

Comments

You could explain a bit more briefly :-)