Given two integers N and K. Create an array of N positive integers such the sum of all elements of the array is divisible by K and therefore the maximum element within the array is that the minimum possible.
You have to seek out the utmost element of that array.
Example:
Input : N=5, K=11 Output : 3 Explanation : We can create the array as [2, 2, 2, 2, 3]. The sum of the array is 11 which is divisible by K=11 and the maximum element is 3 which is minimum possible in this case. Input : N=4, K=3 Output : 2 Explanation : We can create the array as [1, 2, 1, 2]. The sum of the array is 6 which is divisible by K=3 and the maximum element is 2 which is minimum possible in this case.
Approach : Since we have to take all N positive numbers, the minimum value we can assume is 1. The number of arrays is initially N * 1 = N.
Now, there exist two possible cases –
Now, Between the floor value of sum/N and the ceiling value of sum/N, ceil value will be greater. Finally, the maximum element will the ceil value of sum/N.
Below is the implementation of the above approach :
// Java Program to Minimize the maximum element of an array import java.io.*; import java.lang.*; import java.util.*; public class Main { public static void main(String[] args) { // Given int N = 5; int K = 11; System.out.println("N is " +N); System.out.println("K is " +K); // variable sum stores the optimal Sum int sum = 0; // the first case if (K >= N) { // the optimal sum will be K // as we have to keep the sum as minimum as // possible and the sum has to divisible by K sum = K; } // the second case else { // we have to increment sum as // the sum is divisible by K // and sum is greater than or equal to N // the ceiling value of N/K will give the // minimum value that has to be multiplied by K // to get the optimal sum int times = (int)Math.ceil((double)N / (double)K); sum = times * K; } // maximum_element will the ceil value of sum/N int maximum_element = (int)Math.ceil((double)sum / (double)N); // print the maximum_element as answer System.out.println("Maximum element is " +maximum_element); } }
Output
N is 5 K is 11 Maximum element is 3
Time Complexity: O(1)
Auxiliary Space: O(1)