Минимизируйте абсолютную разницу между наименьшими и наибольшими элементами массива с помощью операций минимального приращения и уменьшения
Дан массив arr[] , состоящий из N положительных целых чисел, задача состоит в том, чтобы минимизировать количество операций, необходимых для минимизации абсолютной разницы между наименьшим и наибольшим элементами, присутствующими в массиве. В каждой операции вычитайте 1 из элемента массива и увеличивайте 1 до другого элемента массива.
Примеры:
Input: arr[] = {1, 6}
Output: 2
Explanation:
Below are the operations performed:
Operation 1: Subtracting 1 from 2nd element and adding 1 to 1st element modifies the array to {2, 5}.
Operation2: Subtracting 1 from 2nd element and adding 1 to 1st element modifies the array to {3, 4}.
After the above operations, the absolute difference between the minimum and the maximum element is (4 – 3) = 1, which is minimum and number of operation required is 2.Input: arr[] = {1, 2, 2, 1, 1}
Output: 0
Подход: Данную задачу можно решить, заметив, что увеличение и уменьшение элемента массива на 1 выполняются попарно, поэтому, если сумма элементов массива делится на N , то все элементы массива можно сделать суммой/N . В противном случае некоторые элементы будут иметь значение sum/N , а некоторые элементы будут иметь значение (sum/N + 1) после выполнения данных операций. Выполните следующие шаги, чтобы решить данную проблему:
- Инициализируйте вспомогательный массив, например final[] , в котором хранится результирующий массив с требуемой минимальной разницей.
- Отсортируйте заданный массив в порядке возрастания.
- Пройдите по заданному массиву и, если текущий индекс i меньше sum%N , обновите текущий элемент окончательного массива до значения (sum/N + 1) . В противном случае обновите final[i] до (sum/N) .
- Переверните массив final[].
- Инициализируйте переменную, скажем, ans = 0 , которая хранит минимальное количество операций для преобразования arr[] в final[] .
- Обходим оба массива arr[] и final[] одновременно и добавляем абсолютное значение разницы между arr[i] и final[i] в переменную ans .
- После выполнения вышеуказанных шагов выведите значение an/2 в качестве результирующей минимальной операции.
Ниже приведена реализация вышеуказанного подхода:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to minimize the operations // for the difference between minimum // and maximum element by incrementing // decrementing array elements in pairs void countMinimumSteps( int arr[], int N) { // Stores the sum of the array int sum = 0; // Find the sum of array element for ( int i = 0; i < N; i++) { sum += arr[i]; } // Stores the resultant final array int finalArray[N]; // Iterate over the range [0, N] for ( int i = 0; i < N; ++i) { // Assign values to finalArray if (i < sum % N) { finalArray[i] = sum / N + 1; } else { finalArray[i] = sum / N; } } // Reverse the final array reverse(finalArray, finalArray + N); // Stores the minimum number of // operations required int ans = 0; // Update the value of ans for ( int i = 0; i < N; ++i) { ans += abs (arr[i] - finalArray[i]); } // Print the result cout << ans / 2; } // Driver Code int main() { int arr[] = { 1, 6 }; int N = sizeof (arr) / sizeof (arr[0]); countMinimumSteps(arr, N); return 0; } |
Java
// Java program for the above approach class GFG{ static void reverse( int a[], int n) { int i, k, t; for (i = 0 ; i < n / 2 ; i++) { t = a[i]; a[i] = a[n - i - 1 ]; a[n - i - 1 ] = t; } } // Function to minimize the operations // for the difference between minimum // and maximum element by incrementing // decrementing array elements in pairs static void countMinimumSteps( int arr[], int N) { // Stores the sum of the array int sum = 0 ; // Find the sum of array element for ( int i = 0 ; i < N; i++) { sum += arr[i]; } // Stores the resultant final array int finalArray[] = new int [N]; // Iterate over the range [0, N] for ( int i = 0 ; i < N; ++i) { // Assign values to finalArray if (i < sum % N) { finalArray[i] = sum / N + 1 ; } else { finalArray[i] = sum / N; } } // Reverse the final array reverse(finalArray, finalArray.length); // Stores the minimum number of // operations required int ans = 0 ; // Update the value of ans for ( int i = 0 ; i < N; ++i) { ans += Math.abs(arr[i] - finalArray[i]); } // Print the result System.out.println(ans / 2 ); } // Driver code public static void main(String[] args) { int arr[] = { 1 , 6 }; int N = arr.length; countMinimumSteps(arr, N); } } // This code is contributed by abhinavjain194 |
Python3
# Python program for the above approach # Function to minimize the operations # for the difference between minimum # and maximum element by incrementing # decrementing array elements in pairs def countMinimumSteps(arr, N): # Stores the sum of the array sum = 0 ; # Find the sum of array element for i in range (N): sum + = arr[i]; # Stores the resultant final array finalArray = [ 0 ] * N; # Iterate over the range [0, N] for i in range ( 0 , N): #print(i) # Assign values to finalArray if (i < sum % N): finalArray[i] = ( sum / / N) + 1 ; else : finalArray[i] = sum / / N; # Reverse the final array finalArray = finalArray[:: - 1 ]; # Stores the minimum number of # operations required ans = 0 ; # Update the value of ans for i in range (N): ans + = abs (arr[i] - finalArray[i]); # Print the result print (ans / / 2 ); # Driver Code arr = [ 1 , 6 ]; N = len (arr); countMinimumSteps(arr, N); # This code is contributed by _saurabh_jaiswal. |
C#
// C# program for the above approach using System; class GFG{ static void reverse( int [] a, int n) { int i, t; for (i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } } // Function to minimize the operations // for the difference between minimum // and maximum element by incrementing // decrementing array elements in pairs static void countMinimumSteps( int [] arr, int N) { // Stores the sum of the array int sum = 0; // Find the sum of array element for ( int i = 0; i < N; i++) { sum += arr[i]; } // Stores the resultant final array int [] finalArray = new int [N]; // Iterate over the range [0, N] for ( int i = 0; i < N; ++i) { // Assign values to finalArray if (i < sum % N) { finalArray[i] = sum / N + 1; } else { finalArray[i] = sum / N; } } // Reverse the final array reverse(finalArray, finalArray.Length); // Stores the minimum number of // operations required int ans = 0; // Update the value of ans for ( int i = 0; i < N; ++i) { ans += Math.Abs(arr[i] - finalArray[i]); } // Print the result Console.WriteLine(ans / 2); } // Driver Code public static void Main(String[] args) { int [] arr = { 1, 6 }; int N = arr.Length; countMinimumSteps(arr, N); } } // This code is contributed by target_2 |
Javascript
<script> // Javascript program for the above approach // Function to minimize the operations // for the difference between minimum // and maximum element by incrementing // decrementing array elements in pairs function countMinimumSteps(arr, N) { // Stores the sum of the array let sum = 0; // Find the sum of array element for (let i = 0; i < N; i++) { sum += arr[i]; } // Stores the resultant final array let finalArray = new Array(N); // Iterate over the range [0, N] for (let i = 0; i < N; ++i) { // Assign values to finalArray if (i < sum % N) { finalArray[i] = Math.floor(sum / N + 1); } else { finalArray[i] = Math.floor(sum / N); } } // Reverse the final array finalArray.reverse(); // Stores the minimum number of // operations required let ans = 0; // Update the value of ans for (let i = 0; i < N; ++i) { ans += Math.abs(arr[i] - finalArray[i]); } // Print the result document.write(Math.floor(ans / 2)); } // Driver Code let arr = [1, 6]; let N = arr.length countMinimumSteps(arr, N); // This code is contributed by _saurabh_jaiswal. </script> |
Временная сложность: O (N * log N)
Вспомогательное пространство: O(N)