Maximize element at index K in an array with at most sum M and difference between adjacent elements at most 1
Given a positive integer N, the task is to construct an array of length N and find the 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: The idea is to achieve the maximum value at index K and to decrease the sum of other elements to meet the criteria of the sum of the array to be at most M. Follow the steps below:
- Let the value at index K be X. So the element at K – 1 is X – 1, at K – 2 is X – 2 and so on.
- At index 0 the value is X – K. Similarly, at index K + 1 the value is X – 1 and so on upto X – (N – K – 1) at index N – 1.
- So to achieve the maximum value at index K, the array structure would be X – K, X – (K – 1), …., X – 2, X – 1, X, X – 1, X – 2, ….., X – (N – K – 1).
- So after arranging the equation, it becomes K * X – (1 + 2 + …. + K) + X + (N – K – 1) * X – (1 + 2 + …. + (N – K – 1)) ? M.
Follow the steps to solve the above equation:
- Calculate (1 + 2 + …. + K) using K * (K + 1) / 2 and (1 + 2 + ….. + (N – K – 1)) using (N – K – 1) * (N – K) / 2 and store in S1 and S2 respectively.
- This reduces the equation to X * (K + 1 + N – K – 1) ? M + S1 + S2.
- Now, the maximum value of X can be obtained by calculating (M + S1 + S2) / N.
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 the maximum // possible value at index K void maxValueAtIndexK( int N, int K, int M) { // Stores the sum of elements // in the left and right of index K int S1 = 0, S2 = 0; S1 = K * (K + 1) / 2; S2 = (N - K - 1) * (N - K) / 2; // Stores the maximum // possible value at index K int X = (M + S1 + S2) / N; // Print the answer cout << X; } // Driver Code int main() { // Given N, K & M int N = 3, K = 1, M = 7; maxValueAtIndexK(N, K, M); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG{ // Function to calculate the maximum // possible value at index K static void maxValueAtIndexK( int N, int K, int M) { // Stores the sum of elements // in the left and right of index K int S1 = 0 , S2 = 0 ; S1 = K * (K + 1 ) / 2 ; S2 = (N - K - 1 ) * (N - K) / 2 ; // Stores the maximum // possible value at index K int X = (M + S1 + S2) / N; // Print the answer System.out.println(X); } // Driver Code public static void main(String[] args) { // Given N, K & M int N = 3 , K = 1 , M = 7 ; maxValueAtIndexK(N, K, M); } } // This code is contributed by Dharanendra L V |
Python3
# Python program for the above approach # Function to calculate the maximum # possible value at index K def maxValueAtIndexK(N, K, M): # Stores the sum of elements # in the left and right of index K S1 = 0 ; S2 = 0 ; S1 = K * (K + 1 ) / / 2 ; S2 = (N - K - 1 ) * (N - K) / / 2 ; # Stores the maximum # possible value at index K X = (M + S1 + S2) / / N; # Print the answer print (X); # Driver Code if __name__ = = '__main__' : # Given N, K & M N = 3 ; K = 1 ; M = 7 ; maxValueAtIndexK(N, K, M); # This code is contributed by 29AjayKumar |
C#
// C# program for the above approach using System; class GFG{ // Function to calculate the maximum // possible value at index K static void maxValueAtIndexK( int N, int K, int M) { // Stores the sum of elements // in the left and right of index K int S1 = 0, S2 = 0; S1 = K * (K + 1) / 2; S2 = (N - K - 1) * (N - K) / 2; // Stores the maximum // possible value at index K int X = (M + S1 + S2) / N; // Print the answer Console.WriteLine(X); } // Driver Code static public void Main() { // Given N, K & M int N = 3, K = 1, M = 7; maxValueAtIndexK(N, K, M); } } // This code is contributed by Dharanendra L V |
Javascript
<script> // JavaScript program for // the above approach // Function to calculate the maximum // possible value at index K function maxValueAtIndexK(N, K, M) { // Stores the sum of elements // in the left and right of index K let S1 = 0, S2 = 0; S1 = K * (K + 1) / 2; S2 = (N - K - 1) * (N - K) / 2; // Stores the maximum // possible value at index K let X = (M + S1 + S2) / N; // Print the answer document.write(X); } // Driver Code // Given N, K & M let N = 3, K = 1, M = 7; maxValueAtIndexK(N, K, M); </script> |
3
Time Complexity: O(1)
Auxiliary Space: O(1)