Programa Java para minimizar el elemento máximo de una array

Dados dos enteros N y K. Cree una array de N enteros positivos tal que la suma de todos los elementos de la array sea divisible por K y el elemento máximo en la array sea el mínimo posible.

Tienes que encontrar el elemento Máximo de esa array.

Ejemplo:

 Entrada: N=5, K=11

Salida : 3

Explicación: podemos crear la array como [2, 2, 2, 2, 3]. La suma de la array es 11, que es divisible por K=11 y el elemento máximo es 3, que es el mínimo posible en este caso.

Entrada: N=4, K=3

Salida : 2

Explicación: podemos crear la array como [1, 2, 1, 2]. La suma de la array es 6, que es divisible por K=3 y el elemento máximo es 2, que es el mínimo posible en este caso.

Acercarse : 

Como tenemos que tomar todos los N números positivos, el valor mínimo que podemos tomar es 1. Entonces, inicialmente, la suma de la array es N*1 = N. 

Ahora, existen dos casos posibles:

1. Si K es mayor o igual a N: Si hacemos que la suma de la array sea igual a K, entonces podemos observar que el elemento máximo también se minimizará. Entonces, ahora tenemos que formar una array que consta de N enteros positivos cuya suma es K. Podemos distribuir K/N a todos los N lugares. Si la suma de la array aún no es igual a K, incrementaremos un elemento por K-(N*(K/N)). Por lo tanto, podemos encontrar el mínimo elemento máximo posible. Y estamos distribuyendo valores K/N a cada lugar para que ningún elemento se haga tan grande.
2. Si K es menor que N: dado que la suma inicial es N, hemos incrementado nuestra Suma de tal manera que la Suma sea divisible por K y la Suma sea el mínimo posible. La Suma tiene que ser mínima porque también tenemos que minimizar nuestro elemento máximo. Digamos que la Suma óptima es S. Entonces, S tiene que ser divisible por K y S será mayor o igual que N. Ahora, esto se ha vuelto igual que el primer caso.

Supongamos que, en ambos casos, la suma óptima es S. Entonces, dar el valor mínimo de S/N a N-1 elementos y dar el valor máximo de suma/K al resto del elemento hará que la suma sea igual a S y es también divisible por K.

Ahora, entre el valor mínimo de suma/N y el valor máximo de suma/N, el valor máximo será mayor. Finalmente, el elemento máximo será el valor límite de sum/N. 

A continuación se muestra la implementación del enfoque anterior:

// 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);
    }
}

N is 5
K is 11
Maximum element is 3

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1)