Минимизируйте абсолютную разницу между наименьшими и наибольшими элементами массива с помощью операций минимального приращения и уменьшения

Опубликовано: 22 Сентября, 2022

Дан массив 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)

            

                            

                    
                                    

                        

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