Problem statement
Given an array ‘input[]’ of size ‘size’ with all the integer elements. We are also given a variable ‘X’.We can reduce the different elements of the array by one at most ‘X’ times. The final goal is to find the length of the longest subarray such that all the elements of the subarray are equal after performing the decrement operations.
Example 1
Input
Input[] = { 3, 5, 6, 7, 3 }
Size = 5
K = 3
Output
3
Explanation
There are a lot of possibilities to choose which element to reduce, but we have to choose optimally, so some of the optimal possibilities are
Case 1: reduce index 2 by 1 and reduce index 3 by 2 so total operations for decrement will be 3 and now after decrement array will be like this = {3, 5, 5, 5, 3}. Hence the length of the longest subarray with the same elements is 3
Case 2: reduce index 2 by 2, so total operations for decrement will be 2, which is less than the given value of x that is 3 now after decrement array will be like this = {3, 3, 6, 7, 3}. Hence the length of the longest subarray with the same elements is 2
.
.
Similarly, there are a lot of possibilities we have to find max length subarray, which is the case 1 that is 3.
Approach
To Maximize the length of the longest subarray consisting of the same elements, The idea is to use segment trees and binary search to solve this problem. There is one observation which you will see after working on some test cases that is the Total number of decrements operations required to make all array elements of the subarray { input[start], …, input[end] } equal to (Σ(start, end)) – (end – start + 1) * (minimum value in the subarray). Where start is the starting index of the subarray and end is the ending index of the current subarray on which we are operating. Here we have to reach minimum value in the subarray to make all elements equal for eg if the array is [5,10,15] and we want to make all the elements equal we have to make all the elements as 5 so for that we have to reduce 10 by 5 and 15 by 10 so we took the entire sum which is 30 and subtract min value 5 * (3 - 0) so it will cost 15 operations. which is true we have to decrease 15 10 times and 10 5 times to make all the elements 5. Please try on some test cases and dry run you will get the logic.Below is the detailed algorithm and code for the approach.
Also read, Euclid GCD Algorithm
Algorithm
- Create a segment tree to find the smallest element in a subarray of the array and a prefix sum array to find the sum of the subarray's members.
- Traverse the entire array and Perform the following operations on each element of the array
- Apply binary search throughout the range [start, end] to see if all the items of the subarray input[start],..., input[end] can be made equal or not by decrementing at most X operations from the above observations by setting start = I end = size – 1.
- Update start = (start + end) / 2 + 1 if all the elements of the subarray input[start],..., input[end] can be made equal by decrementing at most X operations.
- Update end = (start + end) / 2 – 1 if not already done.
- Finally, print the length of the longest subarray produced by the preceding procedures.
Code:
// Maximize the length of longest subarray consisting of same elements by at most X decrements
#include <bits/stdc++.h>
using namespace std;
// Segment Tree formation which the minimum element in a range
int buildTree(int segTree[], int* input, int s,int e, int value)
{
// Base case
if (s == e) {
// Update the value in the segment tree from given array
segTree[value] = input[s];
return segTree[value];
}
// Division of left and right subtree
int mid = (s + e) / 2;
// Recursive construction of left sub tree
int leftMin = buildTree(segTree, input, s, mid,2 * value + 1);
// Recursive construction of right subtree
int rightMin = buildTree(segTree, input, mid + 1,e, 2 * value + 2);
// Stores the smallest element in the subarray
return segTree[value] = min(leftMin, rightMin);
}
// This function return smallest element in the sub array
int query(int segTree[], int s, int e,int l, int r, int value)
{
// If the elements are out of range
if (s > r || e < l)return INT_MAX;
/*
If all the elements of the
subarray are in the range [l, r]
*/
if (s >= l && e <= r)
return segTree[value];
// Division of left and right subtree
int mid = (s + e) / 2;
// Smallest element from left subtree
int leftMin = query(segTree, s, mid, l,r, 2 * value + 1);
// Smallest element from right subtree
int rightMin = query(segTree, mid + 1, e, l,r, 2 * value + 2);
return min(leftMin, rightMin);
}
// Maximize the length of longest subarray consisting of same elements by at most X decrements
int solve(int* input, int size, int x)
{
/*
Stores the length of longest subarray with
all the elements equal in atmost x decrements
*/
int ans = 1;
// Store the prefix sum array
int prefixSum[size + 1];
prefixSum[0] = input[0];
for (int i = 0; i < size; i++)
prefixSum[i + 1] = prefixSum[i] + input[i];
int segTree[4 * size + 5];
// Segment tree formation
buildTree(segTree, input, 0, size - 1, 0);
// Iterating the array
for (int i = 0; i < size; i++) {
// start index of the current subarray
int startSub = i;
// end index of the current subarray
int endSub = size - 1;
int mid;
// Stores end index of the longest subarray
int maxSub = i;
// Performing the binary search
while (startSub <= endSub) {
// Find the mid for binary search
mid = (startSub + endSub) / 2;
// Finding the smallest element in range [i, mid] using Segment Tree
int minElement = query(segTree, 0, size - 1, i, mid, 0);
// Stores total sum of subarray after x decrements
int expected_sum = (mid - i + 1) * minElement;
// Stores sum of elements of subarray before x decrements
int actual_sum = prefixSum[mid + 1] - prefixSum[i];
// If subarray found with all equal elements
if (actual_sum - expected_sum <= x) {
// Update start
startSub = mid + 1;
// Update max_index
maxSub = max(maxSub, mid);
}
// This means the selected range is invalid
else {
// Update end
endSub = mid - 1;
}
}
// Store the length of longest subarray
ans = max(ans, maxSub - i + 1);
}
// Return result
return ans;
}
int main()
{
int input[] = { 3,5,6,7,3 };
int x = 3;
int size = 5;
// Maximize the length of longest subarray with at most x decrements
cout << solve(input, size, x);
return 0;
}Output:
|
39+ registered 