0 like 0 dislike
4,554 views
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 .

3)Use Format option while adding code
| 4,554 views

1 like 0 dislike
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  .
by Expert (19,320 points)
1 like 0 dislike
Sort the array , then search position of M in array and then sum previous two elements from that position .
by (190 points)
0 0
You could explain a bit more briefly :-)
0 like 0 dislike
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)
by Expert (610 points)
edited