Рубрики

Минимальные операции, необходимые для изменения массива так, чтобы | arr [i] — M | <= 1

Для заданного массива [] целых чисел задача состоит в том, чтобы найти минимальное количество операций, необходимых для изменения элементов массива, чтобы для любого натурального числа M | arr [i] — M | ≤ 1 для всех действительных я .

В одной операции любой элемент массива может быть увеличен или уменьшен на 1.

Примеры:

Input: arr[] = {10, 1, 4}
Output: 7
If we change 1 into 2 and 10 into 4 with count of operations being |1 – 2| + |10 – 4| = 7
After changing, array becomes {4, 2, 4} where every element’s absolute difference with M = 3 is ≤ 1

Input: arr[] = {5, 7, 4, 1, 4}
Output: 4

Подход: начиная с минимального элемента массива до максимального элемента массива, скажем, num , рассчитайте количество операций, необходимых для изменения каждого элемента, так чтобы его абсолютная разница с num была ≤ 1 . Минимум среди всех возможных операций — это обязательный ответ.

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

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для возврата минимума
// количество необходимых операций

int changeTheArray(int arr[], int n)

{

  

    // Минимальные и максимальные элементы из массива

    int minEle = *(std::min_element(arr, arr + n));

    int maxEle = *(std::max_element(arr, arr + n));

  

    // Для хранения минимального количества

    // необходимые операции

    int minOperations = INT_MAX;

    for (int num = minEle; num <= maxEle; num++) {

  

        // Для хранения необходимого количества операций

        // изменить каждый элемент на

        // (num - 1), num или (num + 1)

        int operations = 0;

        for (int i = 0; i < n; i++) {

  

            // Если текущий элемент еще не num

            if (arr[i] != num) {

  

                // Добавить количество операций

                // требуется изменить arr [i]

                operations += (abs(num - arr[i]) - 1);

            }

        }

  

        // Обновляем минимальное количество операций на данный момент

        minOperations = min(minOperations, operations);

    }

  

    return minOperations;

}

  
// Код драйвера

int main()

{

    int arr[] = { 10, 1, 4 };

    int n = sizeof(arr) / sizeof(arr[0]);

    cout << changeTheArray(arr, n);

  

    return 0;

}

Джава

// Java реализация подхода

import java.util.*;

  

class GFG {

  

    // Функция для возврата минимума

    // количество необходимых операций

    static int changeTheArray(int arr[], int n)

    {

  

        // Минимальные и максимальные элементы из массива

        int minEle = Arrays.stream(arr).min().getAsInt();

        int maxEle = Arrays.stream(arr).max().getAsInt();

  

        // Для хранения минимального количества

        // необходимые операции

        int minOperations = Integer.MAX_VALUE;

        for (int num = minEle; num <= maxEle; num++) {

  

            // Для хранения необходимого количества операций

            // изменить каждый элемент на

            // (num - 1), num или (num + 1)

            int operations = 0;

            for (int i = 0; i < n; i++) {

  

                // Если текущий элемент еще не num

                if (arr[i] != num) {

  

                    // Добавить количество операций

                    // требуется изменить arr [i]

                    operations += (Math.abs(num - arr[i]) - 1);

                }

            }

  

            // Обновляем минимальное количество операций на данный момент

            minOperations = Math.min(minOperations, operations);

        }

  

        return minOperations;

    }

  

    // Код драйвера

    public static void main(String args[])

    {

        int arr[] = { 10, 1, 4 };

        int n = arr.length;

        System.out.println(changeTheArray(arr, n));

    }

}

  
// Этот код предоставлен 29AjayKumar

python3

# Python3 реализация подхода

import math

import sys

  
# Функция для возврата минимума
количество необходимых операций

def changeTheArray(arr, n):

      

    # Минимальные и максимальные элементы

    # из массива

    minEle = min(arr)

    maxEle = max(arr)

  

    # Для хранения минимального количества

    # требуется операций

    minOperations = sys.maxsize

  

    for num in range(minEle, maxEle + 1):

          

        # Для хранения необходимого количества операций

        # чтобы изменить каждый элемент на

        # (число - 1), число или (число + 1)

        operations = 0

        for i in range(n):

  

                # Если текущий элемент еще не num

                if arr[i] != num:

                        operations += (abs(num - arr[i]) - 1)

          

        # Обновление минимального количества операций на данный момент

        minOperations = min(minOperations, operations)

    return minOperations

  
# Код драйвера

if __name__=='__main__':

    arr = [10, 1, 4]

    n = len(arr)

    print(changeTheArray(arr, n))

  
# Этот код предоставлен Викашем Кумаром 37

C #

// C # реализация подхода

using System;

using System.Linq;

  

class GFG 

  

    // Функция для возврата минимума

    // количество необходимых операций

    static int changeTheArray(int []arr, int n) 

    

  

        // Минимальные и максимальные элементы из массива

        int minEle = arr.Min(); 

        int maxEle = arr.Max(); 

  

        // Для хранения минимального количества

        // необходимые операции

        int minOperations = int.MaxValue; 

        for (int num = minEle; num <= maxEle; num++) 

        

  

            // Для хранения необходимого количества операций

            // изменить каждый элемент на

            // (num - 1), num или (num + 1)

            int operations = 0; 

            for (int i = 0; i < n; i++) 

            

  

                // Если текущий элемент еще не num

                if (arr[i] != num)

                

  

                    // Добавить количество операций

                    // требуется изменить arr [i]

                    operations += (Math.Abs(num - arr[i]) - 1); 

                

            

  

            // Обновляем минимальное количество операций на данный момент

            minOperations = Math.Min(minOperations, operations); 

        

  

        return minOperations; 

    

  

    // Код драйвера

    public static void Main(String []args) 

    

        int []arr = { 10, 1, 4 }; 

        int n = arr.Length; 

        Console.WriteLine(changeTheArray(arr, n)); 

    

  
// Этот код предоставлен Rajput-Ji

Выход:

7

Рекомендуемые посты:

Минимальные операции, необходимые для изменения массива так, чтобы | arr [i] — M | <= 1

0.00 (0%) 0 votes