Maximize value at Kth index to create N size array with adjacent difference 1 and sum less than M | C ++ 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 . ; variable to store final answer ; variables for binary search ; Binary search ; variable for binary search ; variable to store total sum of array ; number of indices on the left excluding the Kth index ; number of indices on the left excluding the Kth index ; add mid to final sum ; distribution on left side is possible ; sum of distribution on the left side ; sum of distribution on the left side with ( L - mid ) 1 s ; distribution on right side is possible ; sum of distribution on the right side ; sum of distribution on the left side with ( R - mid ) 1 s ; Distribution is valid ; return answer ; Driver code ; Input ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int calculateMax ( int N , int M , int K ) { int ans = -1 ; int low = 0 , high = M ; while ( low <= high ) { int mid = ( low + high ) / 2 ; int val = 0 ; int L = K - 1 ; int R = N - K ; val += mid ; if ( mid >= L ) { val += ( L ) * ( 2 * mid - L - 1 ) / 2 ; } else { val += mid * ( mid - 1 ) / 2 + ( L - mid ) ; } if ( mid >= R ) { val += ( R ) * ( 2 * mid - R - 1 ) / 2 ; } else { val += mid * ( mid - 1 ) / 2 + ( R - mid ) ; } if ( val <= M ) { ans = max ( ans , mid ) ; low = mid + 1 ; } else high = mid - 1 ; } return ans ; } int main ( ) { int N = 7 , M = 100 , K = 6 ; cout << calculateMax ( N , M , K ) << endl ; return 0 ; }