Given three numbers N, K, and M, the task is to find the maximum value that can be assigned to the Kth index if positive values are assigned to all N indices such that the total sum of values is less than M, and the difference between the values at adjacent positions is atmost 1.
Examples:
Input : N=3, M=10, K=2
Output: 4
Explanation: The optimal way to assign values is {3, 4, 3}. Total sum=3+4+3=10≤M.
Note: {3, 4, 2} is not a valid distribution as 4-2=2>1Input: N=7, M=100, K=6
Output: 16
Approach : The following observations help in solving the problem:
- If X is assigned at the Kth index, then, the optimal distribution is as follows:
- If X is less than K-1, the optimal distribution on than left would be (X-1), (X-2), …(X-K+1), (1), (1)…
- Otherwise, it would be (X-1), (X-2), …(X-K+1).
- If X is less than N-K, the optimal distribution on than left would be (X-1), (X-2), …(X-N+K), 1, 1…
- Otherwise, it would be (X-1), (X-2), …(X-N+K).
- Using the AP series, the sum of (X-1)+(X-2)+(X-3)+…+(X-Y) is Y*(X-1+X-Y)/2 = Y*(2X-Y-1)/2
The maximum value of X can be calculated with the concept of Binary search. Follow the steps below to solve the problem:
- Initialize a variable ans to -1, to store the answer.
- Initialize two variables low to 0 and high to M, for the purpose of binary searching.
- Loop while low is not greater than high and do the following:
- Calculate mid as the mean of high and low.
- Initialize a variable val to 0, to store current sum of distribution.
- Initialize L(number of indices on the left of K) as K-1 and R(number of indices on the right of K) as N-K.
- Add the value of mid to val.
- Distribute numbers on the left and right of K as discussed above and add their values to val.
- If val is less than M, update ans as the maximum of ans and mid. Update low as mid+1.
- Otherwise, update high as mid-1.
- Return ans.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate maximum value that can be placed at// the Kth index in a distribution in which difference of// adjacent elements is less than 1 and total sum of// distribution is M.int calculateMax(int N, int M, int K){ // variable to store final answer int ans = -1; // variables for binary search int low = 0, high = M; // Binary search while (low <= high) { // variable for binary search int mid = (low + high) / 2; // variable to store total sum of array int val = 0; // number of indices on the left excluding the Kth // index int L = K - 1; // number of indices on the left excluding the Kth // index int R = N - K; // add mid to final sum val += mid; // distribution on left side is possible if (mid >= L) { // sum of distribution on the left side val += (L) * (2 * mid - L - 1) / 2; } else { // sum of distribution on the left side with // (L-mid) 1s val += mid * (mid - 1) / 2 + (L - mid); } // distribution on right side is possible if (mid >= R) { // sum of distribution on the right side val += (R) * (2 * mid - R - 1) / 2; } else { // sum of distribution on the left side with // (R-mid) 1s val += mid * (mid - 1) / 2 + (R - mid); } // Distribution is valid if (val <= M) { ans = max(ans, mid); low = mid + 1; } else high = mid - 1; } // return answer return ans;}// Driver codeint main(){ // Input int N = 7, M = 100, K = 6; // Function call cout << calculateMax(N, M, K) << endl; return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to calculate maximum value that can be // placed at // the Kth index in a distribution in which difference // of adjacent elements is less than 1 and total sum of // distribution is M. public static int calculateMax(int N, int M, int K) { // variable to store final answer int ans = -1; // variables for binary search int low = 0, high = M; // Binary search while (low <= high) { // variable for binary search int mid = (low + high) / 2; // variable to store total sum of array int val = 0; // number of indices on the left excluding the // Kth index int L = K - 1; // number of indices on the left excluding the // Kth index int R = N - K; // add mid to final sum val += mid; // distribution on left side is possible if (mid >= L) { // sum of distribution on the left side val += (L) * (2 * mid - L - 1) / 2; } else { // sum of distribution on the left side with // (L-mid) 1s val += mid * (mid - 1) / 2 + (L - mid); } // distribution on right side is possible if (mid >= R) { // sum of distribution on the right side val += (R) * (2 * mid - R - 1) / 2; } else { // sum of distribution on the left side with // (R-mid) 1s val += mid * (mid - 1) / 2 + (R - mid); } // Distribution is valid if (val <= M) { ans = Math.max(ans, mid); low = mid + 1; } else high = mid - 1; } // return answer return ans; } // Driver code public static void main(String[] args) { // Input int N = 7, M = 100, K = 6; // Function call System.out.println(calculateMax(N, M, K)); }}// This code is contributed by lokeshpotta20. |
Python3
# Python3 program for the above approach# Function to calculate maximum value # that can be placed at the Kth index # in a distribution in which difference # of adjacent elements is less than 1 # and total sum of distribution is M.def calculateMax(N, M, K): # Variable to store final answer ans = -1 # Variables for binary search low = 0 high = M # Binary search while (low <= high): # Variable for binary search mid = (low + high) / 2 # Variable to store total sum of array val = 0 # Number of indices on the left excluding # the Kth index L = K - 1 # Number of indices on the left excluding # the Kth index R = N - K # Add mid to final sum val += mid # Distribution on left side is possible if (mid >= L): # Sum of distribution on the left side val += (L) * (2 * mid - L - 1) / 2 else: # Sum of distribution on the left side # with (L-mid) 1s val += mid * (mid - 1) / 2 + (L - mid) # Distribution on right side is possible if (mid >= R): # Sum of distribution on the right side val += (R) * (2 * mid - R - 1) / 2 else: # Sum of distribution on the left side with # (R-mid) 1s val += mid * (mid - 1) / 2 + (R - mid) # Distribution is valid if (val <= M): ans = max(ans, mid) low = mid + 1 else: high = mid - 1 # Return answer return int(ans)# Driver code# InputN = 7M = 100K = 6# Function callprint(calculateMax(N, M, K));# This code is contributed by sanjoy_62 |
C#
// C# program for the above approachusing System;class GFG{ // Function to calculate maximum value that can be // placed at // the Kth index in a distribution in which difference // of adjacent elements is less than 1 and total sum of // distribution is M. public static int calculateMax(int N, int M, int K) { // variable to store final answer int ans = -1; // variables for binary search int low = 0, high = M; // Binary search while (low <= high) { // variable for binary search int mid = (low + high) / 2; // variable to store total sum of array int val = 0; // number of indices on the left excluding the // Kth index int L = K - 1; // number of indices on the left excluding the // Kth index int R = N - K; // add mid to final sum val += mid; // distribution on left side is possible if (mid >= L) { // sum of distribution on the left side val += (L) * (2 * mid - L - 1) / 2; } else { // sum of distribution on the left side with // (L-mid) 1s val += mid * (mid - 1) / 2 + (L - mid); } // distribution on right side is possible if (mid >= R) { // sum of distribution on the right side val += (R) * (2 * mid - R - 1) / 2; } else { // sum of distribution on the left side with // (R-mid) 1s val += mid * (mid - 1) / 2 + (R - mid); } // Distribution is valid if (val <= M) { ans = Math.Max(ans, mid); low = mid + 1; } else high = mid - 1; } // return answer return ans; }// Driver codestatic void Main(){ // Input int N = 7, M = 100, K = 6; // Function call Console.Write(calculateMax(N, M, K));}}// This code is contributed by code_hunt. |
Javascript
<script> // JavaScript program for the above approach // Function to calculate maximum value that can be placed at // the Kth index in a distribution in which difference of // adjacent elements is less than 1 and total sum of // distribution is M. function calculateMax(N, M, K) { // variable to store final answer var ans = -1; // variables for binary search var low = 0, high = M; // Binary search while (low <= high) { // variable for binary search var mid = parseInt((low + high) / 2); // variable to store total sum of array var val = 0; // number of indices on the left excluding the Kth // index var L = K - 1; // number of indices on the left excluding the Kth // index var R = N - K; // add mid to final sum val += mid; // distribution on left side is possible if (mid >= L) { // sum of distribution on the left side val += (L) * ((2 * mid - L - 1) / 2); } else { // sum of distribution on the left side with // (L-mid) 1s val += mid * parseInt((mid - 1) / 2) + (L - mid); } // distribution on right side is possible if (mid >= R) { // sum of distribution on the right side val += (R) * (2 * mid - R - 1) / 2; } else { // sum of distribution on the left side with // (R-mid) 1s val += mid * parseInt((mid - 1) / 2) + (R - mid); } // Distribution is valid if (val <= M) { ans = Math.max(ans, mid); low = mid + 1; } else high = mid - 1; } // return answer return ans; } // Driver code // Input let N = 7, M = 100, K = 6; // Function call document.write(calculateMax(N, M, K));// This code is contributed by lokeshpotta20. </script> |
Output
16
Time Complexity: O(LogM)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
