For all algorithms give the analysis for the worst-case time bound. Read the pro

Question

For all algorithms give the analysis for the worst-case time bound. Read the problem statements carefully. You cannot use hashing.

Given is an array A of size n containing positive integers in arbitrary order and an integer T. Describe and analyze an efficient algorithm determining whether there exist two indices i and j, 1 i < j n, such that A[i] + A[i + 1] + . . . + A[j] T. When a solution exists, determine the one with j i a maximum over all solutions. For example, consider A = [1, 21, 2, 22, 3, 23, 4, 24, 5]; T=10 has no solution; T = 22 has one solution (i=1 and j=2); T=25 has a solution consisting of 3 elements (1+21+2).

Explanation / Answer

Hi, Please find my algorithm.

It is based on Binary Search.

Algorithm:

since all the array element are positive integers, we can say that the prefix sum of any subarray shall be strictly increasing.
Thus, we can say that

if arr[i] + arr[i + 1] + ..... + arr[j - 1] + arr[j] <= K
then arr[i] + arr[i + 1] + ..... + arr[j - 1] <= K, as
arr[j] is a positive integer.

we perform Binary Search over the range 1 to n and find the highest subarray size
such that all the subarrays of that size have sum of elements less than k.

// Return the maximum subarray size, such that
// all subarray of that size have sum less than K.
int maxSize(int arr[], int n, int k)
{
int prefixsum[n+1];

// Finding prefix sum of the array.
for (int i = 0; i < n; i++)
prefixsum[i+1] = prefixsum[i] + arr[i];

return bsearch(prefixsum, n, k);
}

// Search for the maximum length of required
// subarray.
int bsearch(int prefixsum[], int n, int k)
{
int ans = -1; // Initialize result

// Do Binary Search for largest subarray size
int left = 1, right = n;
while (left <= right)
{
int mid = (left + right)/2;

// Check for all subarrays after mid
int i;
for (i = mid; i <= n; i++)
{
// Checking if all the subarrays of a size
// is less than k.
if (prefixsum[i] - prefixsum[i - mid] > k)
break;
}

// All subarrays of size mid have sum less
// than or equal to k
if (i == n+1)
{
left = mid + 1;
ans = mid;
}

// We found a subrray of size mid with sum
// greater than k
else
right = mid -1;
}

return ans;
}

Time Complexity : O(n log n).

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.