Given two positive integers N and K, the task is to minimize the maximum element of the array formed such that the sum of array elements is positive and divisible by K.
Examples:
Input: N = 4, K = 50
Output: 13
Explanation The generated array is {12, 13, 12, 13}. Sum of the array is 50, which is divisible by K (= 50). Maximum element present in the array is 13, which is minimum possible.Input: N = 3, K = 3
Output: 1
Approach: The given problem can be solved on the basis of the following observations:
- To minimize the maximum element of the array, the absolute difference of each pair of array elements must be at most 1 and sum of array elements must be K.
- Therefore, the value of all the N element must be at least equal to the floor value of (K/N) and the increment the remaining (K%N) elements by 1 to make the sum of array element K.
From the above observations, the minimized maximum value of the constructed array is the ceil value of (K/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 minimize the maximum// element present in an N-length array// having sum of elements divisible by Kint minimumValue(int N, int K){ // Return the ceil value of (K / N) return ceil((double)K / (double)N);}// Driver Codeint main(){ int N = 4, K = 50; cout << minimumValue(N, K); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to minimize the maximum// element present in an N-length array// having sum of elements divisible by Kstatic int minimumValue(int N, int K){ // Return the ceil value of (K / N) return(int)Math.ceil((double)K / (double)N);}// Driver codepublic static void main(String[] args){ int N = 4, K = 50; System.out.print(minimumValue(N, K));}}// This code is contributed by code_hunt. |
Python3
# Python3 program for the above approachimport math# Function to minimize the maximum# element present in an N-length array# having sum of elements divisible by Kdef minimumValue(N, K): # Return the ceil value of (K / N) return math.ceil(K / N)# Driver CodeN = 4K = 50print(minimumValue(N, K))# This code is contributed by abhinavjain194 |
C#
// C# program for the above approachusing System;class GFG{// Function to minimize the maximum// element present in an N-length array// having sum of elements divisible by Kstatic int minimumValue(int N, int K){ // Return the ceil value of (K / N) return(int)Math.Ceiling((double)K / (double)N);}// Driver Codepublic static void Main(){ int N = 4, K = 50; Console.WriteLine(minimumValue(N, K));}}// This code is contributed by ukasp |
Javascript
<script>// javascript program for the above approach// Function to minimize the maximum// element present in an N-length array// having sum of elements divisible by Kfunction minimumValue(N, K){ // Return the ceil value of (K / N) return Math.ceil(K / N);}// Driver Code let N = 4, K = 50; document.write(minimumValue(N, K));</script> |
Output:
13
Time Complexity: O(1)
Auxiliary Space: O(1)
