Rendre les éléments du tableau égaux avec un coût minimum

Étant donné un tableau d’entiers arr[]la tâche consiste à trouver le nombre minimum d’étapes pour rendre les éléments du tableau égaux en suivant deux opérations –

  • Ajouter ou soustraire 2 de l’élément avec 0 Coût
  • Ajouter ou soustraire 1 de l’élément avec 1 Coût

Exemples:

Saisir: arr[] = {4, 3, 2, 1}
Production: 2
Explication:
Comme dans l’exemple ci-dessus, tous les éléments du tableau peuvent être égaux à 4 ou 3 avec 2 comme coût minimum
Coût de création d’éléments de tableau égal à 4
Indice 0 : Comme l’indice 0 est déjà égal à 4, le coût est 0
Indice 1 : 4 – 3 = 1, Ajouter 1 à l’élément coûtera 1
Indice 2 : 4 – 2 = 2, Ajouter 2 à l’élément coûtera 0
Indice 3 : 4 – 1 = 3, Ajoutez 2 et 1 une fois dans l’élément de tableau, ce qui coûtera 1car 2 peut être ajouté un nombre quelconque de fois avec un coût de 0.
Coût total = 1 + 1 = 2

Saisir: arr[] = {3, 2, 1}
Production: 1
Explication:
Comme dans l’exemple ci-dessus, tous les éléments du tableau peuvent être rendus égaux à 3 ou 1 avec 1 comme coût minimum
Coût de création d’éléments de tableau égal à 3
Indice 0 : Comme l’indice 0 est déjà égal à 3, le coût est 0
Indice 1 : 3 – 2 = 1, Ajouter 1 à l’élément coûtera 1
Indice 2 : 3 – 1 = 2, Ajouter 2 à l’élément coûtera 0
Coût total = 1

Approcher: L’idée est d’utiliser le fait que l’ajout de 2 à n’importe quel élément du tableau coûtera 0. Aussi la deuxième observation est que l’ajout de 2 à n’importe quel nombre impair se traduira par un nombre impair et de même l’ajout de 2 à un nombre pair se traduira par un nombre pair uniquement. Par conséquent, tout élément peut être rendu égal à un entier le plus proche à un coût nul mais avec la même propriété qu’il restera impair s’il est impair comme valeur initiale ou il restera même s’il est pair comme valeur initiale. Ainsi, pour trouver le coût minimum, nous pouvons trouver le nombre minimum d’éléments pairs ou impairs dans le tableau.

Algorithme:

  • Trouvez le nombre d’éléments pairs ou impairs dans le tableau (disons compter).
  • Trouver la valeur minimale entre count et (length – count) où longueur est la longueur du tableau.
  • La valeur minimale sera le coût souhaité pour que tous les éléments du tableau soient égaux.

Explication avec exemple :

Given Array be  - {4, 2, 3, 1}
Count of Odd Elements - 2 ({3, 1})
Count of Even Elements - 2 ({4, 2})

Hence, the minimum cost required is 2 and
the array elements can be made equal 
to any integer of even or odd value

Voici la mise en œuvre de l’approche ci-dessus :

C++

#include <bits/stdc++.h>

using namespace std;

void makearrayequal(int arr[], int n)

{

    int x = 0;

    

    

    

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

        x += arr[i] & 1;

    }

    cout << min(x, n - x) << endl;

}

int main()

{

    int arr[] = { 4, 3, 2, 1 };

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

    makearrayequal(arr, n);

    return 0;

}

Java

class GFG {

    

    

    

    static void makearrayequal(int arr[], int n)

    {

        int x = 0;

        

        

        

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

            x += (arr[i] & 1);

        }

    

        System.out.println(Math.min(x, n - x));

    }

    

    

    public static void main (String[] args)

    {

        int arr[] = { 4, 3, 2, 1 };

        int n = arr.length;

        makearrayequal(arr, n);

       

    }

}

Python3

def makearrayequal(arr,  n) :

    x = 0;

    

    

    

    for i in range(n) :

        x += arr[i] & 1;

    print(min(x, n - x));

if __name__ == "__main__" :

    arr = [ 4, 3, 2, 1 ];

    n = len(arr);

    makearrayequal(arr, n);

  

C#

using System;

class GFG {

    

    

    

    static void makearrayequal(int []arr, int n)

    {

        int x = 0;

        

        

        

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

            x += (arr[i] & 1);

        }

    

        Console.WriteLine(Math.Min(x, n - x));

    }

    

    

    public static void Main (string[] args)

    {

        int []arr = { 4, 3, 2, 1 };

        int n = arr.Length;

        makearrayequal(arr, n);

       

    }

}

Javascript

<script>

function makearrayequal(arr , n)

{

    var x = 0;

    

    

    

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

    {

        x += (arr[i] & 1);

    }

    document.write(Math.min(x, n - x));

}

var arr = [ 4, 3, 2, 1 ];

var n = arr.length;

makearrayequal(arr, n);

</script>

Analyse de performance:

  • Complexité temporelle : SUR).
  • Espace Auxiliaire : O(1)

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Aller en haut