Программа на Java для минимизации максимального элемента массива

Опубликовано: 30 Ноября, 2021

Даны два целых числа N и K. Создайте массив из N положительных целых чисел так, чтобы сумма всех элементов массива делилась на K, а максимальный элемент в массиве был минимально возможным.

Вам нужно найти максимальный элемент этого массива.

Пример:

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.

Подход :

Поскольку мы должны принять все N чисел положительными, поэтому минимальное значение, которое мы можем принять, равно 1. Итак, изначально сумма массива равна N * 1 = N.

Теперь существует два возможных случая -

Если K больше или равно N: если мы сделаем сумму массива равной K, то мы увидим, что максимальный элемент также будет минимизирован. Итак, теперь мы должны сформировать массив, состоящий из N натуральных чисел, сумма которых равна K. Мы можем распределить K / N по всем N местам. Если сумма массива все еще не равна K, тогда мы увеличим один элемент на K- (N * (K / N)). Таким образом, мы можем найти минимально возможный максимальный элемент. И мы распределяем значения K / N для каждого места, чтобы ни один элемент не стал таким большим.
Если K меньше N: поскольку начальная сумма равна N, мы увеличиваем нашу Sum так, чтобы Sum делилась на K, а Sum была минимально возможной. Сумма должна быть минимальной, потому что мы также должны минимизировать наш максимальный элемент. Скажем, оптимальная сумма равна S. Итак, S должно делиться на K, а S будет больше или равно N. Теперь это то же самое, что и в первом случае.

Пусть в обоих случаях Оптимальная сумма равна S. Таким образом, присвоение минимального значения S / N N-1 элементам и значение ceil суммы / K остальному элементу сделает сумму равной S, и это будет также делится на К.

Теперь между минимальным значением sum / N и максимальным значением sum / N значение ceil будет больше. Наконец, максимальный элемент будет иметь максимальное значение sum / N.

Ниже представлена реализация описанного выше подхода:

Ява

 // 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 равно 5
K равно 11
Максимальный элемент - 3

Сложность времени: O (1)

Вспомогательное пространство: O (1)

Вниманию читателя! Не прекращайте учиться сейчас. Ознакомьтесь со всеми важными концепциями Java Foundation и коллекций с помощью курса "Основы Java и Java Collections" по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Technical Scripter Java

Программа на Java для минимизации максимального элемента массива

Ява

РЕКОМЕНДУЕМЫЕ СТАТЬИ