MDSA - Editorial

general
, ,
1

PROBLEM LINK:

Practice

Contest

Author: Md Shahid

Tester: Arkapravo Ghosh

Editorialist: Md Shahid

DIFFICULTY:

EASY

PREREQUISITES:

Binary Search

PROBLEM:

you have been given an array A(indexed 1 through N). There is a thresold value Th. You need to find a maximum integer value M so that S is greater or equal to Th. Where,
S = \sum_{i=1}^{N} max(A_i-M,0).

You need to find maximum value M and sum S.

QUICK EXPLANATION:

This problem can be easily solved by Binary Search algorithm. First of all sort the given array in ascending order. Then run the loop from N-1 to 0.If the sum is greater than or equal to M, assign low with mid+1 otherwise high will be updated with mid. After the completion of loop answer will be low - 1.

EXPLANATION:

This problem is solely based binary search algorithm. First of all let’s talk about what we do in binary search algorithm then we will relate this problem with binary search and how can we solve this problem with that.

Binary Search Algorithm

Binary search applies to only sorted array.Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.Here A is the array, x is the element you want to find i.e, key, low is the left most index and high is right most index of array.
Binary_Search ( A, x, high, low)

  • while ( low <= high )
  • mid = (low + high)/2 // Finding middle position of array
  • if ( A[mid] == x) // If the search element is found at mid position return mid
  • return mid and end if
  • if ( A[mid] < x)
  • low = mid + 1
  • else high = mid - 1
  • End if
  • End while
  • return -1 // if the element is not found

I hope through this explanation you have a better understanding of binary search. Now let’s jump into our question. In this problem we need to find the maximum M so that sum S is greater equal to threshold Th.

Algorithm

  • sort the array
  • Run a binary search with values low=0 and high=length[n-1], such that mid=(low+high)/2.
  • Run a loop fron N-1 to 0 and adding max(A_i-mid, 0)
  • If the sum is greater than or equal to M, assign low with mid+1 otherwise high will be updated with mid.
  • After Binary search is completed the answer will be low-1.
  • Once we have calculated M successfully we can easily can calculate S by running a loop separately.

Time Complexity :

As the time complexity of binary search is O(N). But there is an extra loop within binary search
function so the time complexity of this algorithm will be O(N*logN).

AUTHOR’S AND EDITORIALIST’S SOLUTIONS:

Author’s and editorialist’s solution can be found here.

1 Like