Given a positive integer N, the task is to construct an array of length N and maximize the value at index K such that the sum of all the array elements is at most M and the absolute difference between any two consecutive array elements is at most 1.
Examples:
Input: N = 3, M = 7, K = 1
Output: 3
Explanation: According to the given constraints, the array with values {2, 3, 2} maximizes the value at index 1. Therefore, the required output is 3.
Input: N = 3, M = 8, K = 1
Output: 3
Approach:
Given problem’s approach can be understood by taking the input example of N = 10 and K = 7 and following the steps to maximize K:
- [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] ——> Maximizing K with 1
- [1, 1, 1, 1, 1, 1, 2, 1, 1, 1] ——> Maximizing K with 2
- [1, 1, 1, 1, 1, 2, 3, 2, 1, 1] ——> Maximizing K with 3
- [1, 1, 1, 1, 2, 3, 4, 3, 2, 1] ——> Maximizing K with 4
- [1, 1, 1, 2, 3, 4, 5, 4, 3, 2] ——> Maximizing K with 5
With all these examples it is clear that to maximize the value at K we fill the array decreasing order in left( K- 1) and in right (K + 1).
Assuming F(x) is the function that gives us this sum of the array when we try to fill X at the Kth position of the array.
Properties of this Function.
- Strictly Increasing Function because the sum will only increase with increasing value of X.
- depends on 3 arguments ( N, K, X ).
- We know that N is constant, K is Constant So we can say it depends on only X.
Naïve Approach:
- Try X = 1
- F(X) = Y
- If (Y == maxSum) then return X as output.
- else we try with X + 1 and repeat above process until we get F[ X ] == maxSum then we return X.
- else if F[X+1] > maxSum then we return X.
Efficient Approach:
Binary Search (Since F[X] is increasing Function we Apply binary search). With little observation we can see low = 1 (when maxSum == N ) and high = maxSum ( when N == 1 ).
while( low <= high) {
mid = (low + ( high – low)/2)
If( F[mid] == maxSum) return mid;
else if( F[mid] < maxSum) low = mid+1
else high = mid-1
}
Let Sm be the sum of first n natural numbers Sm = n * (n+1) / 2
Right side = ( N-K+1)
Left side = K
Let N_ = arbitrary increasing sequence of length N_
case 1 : N_ <= min( Left_side, Right_side)
F[x] = Sm( N_ )*2 – N_ + ( N- 2*N_+1)
case 2 : N_ <= max( Left_side, Right_side)
F[x] = Sm( N_ )*2 – N_ – Sm( N_ – min(right, left) ) + ( N + 1 – ( 2*N_ – ( N- min(left, right) ) ) )
case 3 : N_ > max( Left_side, Right_side)
F[x] = Sm( N_ )*2 – N_ – Sm( N_ – left ) – Sm(N_ – right)
Here is the implementation of the above approach in C++ –
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll N;
ll K;
// Helper function to return the minimum value
ll min(ll a, ll b) {
return (a <= b) ? a : b;
}
// Helper function to return the maximum value
ll max(ll a, ll b) {
return (a >= b) ? a : b;
}
// Helper function to return the sum of the first n natural numbers
ll Sm(ll n) {
return (n * (n + 1)) / 2;
}
// Helper function to return the sum of the array with the desired value of K
ll F(ll x) {
if (x == 0) {
return 0;
}
ll left = K;
ll right = N - K + 1;
ll Y = 0;
if (x <= min(left, right)) {
Y = Sm(x) * 2 - x + (N - 2 * x + 1);
} else if (x <= max(left, right)) {
Y = Sm(x) * 2 - x - Sm(x - min(left, right)) + (N + 1 - (2 * x - (x - min(left, right))));
} else {
Y = Sm(x) * 2 - (x + Sm(x - right) + Sm(x - left));
}
return Y;
}
// Helper function to print the resultant array
void print_array(ll a, ll K, ll n) {
vector<int> arr(n + 2);
for (int i = K; i >= 1; i--) {
arr[i] = a;
if (a < 1) arr[i] = 1;
a--;
}
a += K;
a--;
for (int i = K + 1; i <= n; i++) {
arr[i] = a;
if (a < 1) arr[i] = 1;
a--;
}
for (int i = 1; i <= n; i++) {
cout << arr[i] << " ";
}
cout << '\n';
}
int main() {
// Note: maxSum should be >= N because the lowest value the array can get is 1.
N = 7;
K = 5;
ll maxSum = 130;
int test = 1;
// Uncomment the below line to test it with different test cases for N, K, maxSum input.
// Remember maxSum >= N.
// while (cin >> N >> K >> maxSum) {
while (test--) {
if (maxSum < N) {
cout << "Try with maxSum >= N\n";
continue;
}
ll low = 1;
ll high = maxSum;
ll mid;
ll ans = low;
ll Y;
while (low <= high) {
mid = low + (high - low) / 2;
Y = F(mid); // Save the value because we need to make two comparisons in the worst case
if (Y == maxSum) {
ans = mid; // If the array sum is exact, then we cannot find a better value
break;
} else if (Y < maxSum) {
ans = mid;
low = mid + 1; // Save this partial result in case we don't get an exact match
} else {
high = mid - 1;
}
}
cout << "Max Value at K " << ans << endl;
cout << "Array: ";
print_array(ans, K, N);
cout << "Reached Sum: " << F(ans) << endl;
cout << "Unused Sum: " << maxSum - F(ans) << endl;
}
return 0;
}