Maximize value at Kth index to create N size array with adjacent difference 1 and sum less than M

0 0 9 minutes read

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>1

Input: 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:
1. If X is less than K-1, the optimal distribution on than left would be (X-1), (X-2), …(X-K+1), (1), (1)…
2. Otherwise, it would be (X-1), (X-2), …(X-K+1).
3. If X is less than N-K, the optimal distribution on than left would be (X-1), (X-2), …(X-N+K), 1, 1…
4. 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:
1. Calculate mid as the mean of high and low.
2. Initialize a variable val to 0, to store current sum of distribution.
3. 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.
4. Add the value of mid to val.
5. Distribute numbers on the left and right of K as discussed above and add their values to val.
6. If val is less than M, update ans as the maximum of ans and mid. Update low as mid+1.
7. 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 code
int 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 approach
import 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
 
# Input
N = 7
M = 100
K = 6
 
# Function call
print(calculateMax(N, M, K));
 
# This code is contributed by sanjoy_62

C#

// C# program for the above approach
using 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 code
static 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

Time Complexity: O(LogM)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!