Valor mínimo de X para hacer que todos los elementos de la array sean iguales al disminuir o aumentar en X

    Dada una array de N elementos, puede realizar dos operaciones en ella:
  • Aumente cualquiera de los elementos de la array en X una vez.
  • Disminuya cualquiera de los elementos de la array en X una vez.

La tarea es encontrar el valor máximo mínimo de X tal que todos los elementos de la array sean iguales aplicando la operación 1, 2 o no aplicando ninguna operación. Si no se pueden hacer iguales todos los elementos de la array, imprima -1.

Ejemplos:

Entrada: a[] = {1, 4, 4, 7, 4, 1}
Salida: 3
Aumenta el primer y último elemento en 3.
Disminuye el cuarto elemento en 3.

Entrada: {1, 5, 7, 9, 1}
Salida: -1

Enfoque : dado que las operaciones de incremento en X y decremento en X solo se pueden aplicar una vez en un elemento de array, el punto común de observación es que si hay más de 3 elementos únicos que la respuesta es -1, pueden surgir tres casos que se resuelven de las siguientes maneras:

  • Si hay 3 elementos únicos, si abs(el2-el1) == abs(el3-el2) , entonces la respuesta es abs(el2-el1) . Si no son iguales, la respuesta es -1.
  • Si hay 2 elementos únicos, la respuesta es (el2 – el1) / 2 , si el2 – el1 es par, de lo contrario, la respuesta es (el2 – el1)
  • Si hay un solo elemento único, entonces la respuesta es 0

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program to implement
// the above approach
  
#include <bits/stdc++.h>
using namespace std;
  
// Function that returns the
// minimum value of X
int findMinimumX(int a[], int n)
{
  
    // Declare a set
    set<int> st;
  
    // Iterate in the array element
    // and insert them into the set
    for (int i = 0; i < n; i++)
        st.insert(a[i]);
  
    // If unique elements is 1
    if (st.size() == 1)
        return 0;
  
    // Unique elements is 2
    if (st.size() == 2) {
        // Get both el2 and el1
        int el1 = *st.begin();
        int el2 = *st.rbegin();
  
        // Check if they are even
        if ((el2 - el1) % 2 == 0)
            return (el2 - el1) / 2;
        else
            return (el2 - el1);
    }
  
    // If there are 3 unique elements
    if (st.size() == 3) {
        // Get three unique elements
        auto it = st.begin();
        int el1 = *it;
        it++;
        int el2 = *it;
        it++;
        int el3 = *it;
  
        // Check if their difference is same
        if ((el2 - el1) == (el3 - el2))
            return el2 - el1;
        else
            return -1;
    }
  
    // More than 3 unique elements
    return -1;
}
  
// Driver code
int main()
{
    int a[] = { 1, 4, 4, 7, 4, 1 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << findMinimumX(a, n);
  
    return 0;
}

Java

// Java implementation of the approach
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
  
class GFG 
{
      
    // Function that returns the
    // minimum value of X
    static int findMinimumX(int a[], int n)
    {
  
        // Declare a set
        Set<Integer> st = new HashSet<>();
  
        // Iterate in the array element
        // and insert them into the set
        for (int i = 0; i < n; i++)
            st.add(a[i]);
  
        // If unique elements is 1
        if (st.size() == 1)
            return 0;
  
        // Unique elements is 2
        if (st.size() == 2) 
        {
            // Get both el2 and el1
            Iterator<Integer> it = st.iterator();
            int el1 = it.next();
            int el2 = it.next();
  
            // Check if they are even
            if ((el2 - el1) % 2 == 0)
                return (el2 - el1) / 2;
            else
                return (el2 - el1);
        }
  
        // If there are 3 unique elements
        if (st.size() == 3) 
        {
            // Get three unique elements
            Iterator<Integer> it = st.iterator();
            int el1 = it.next();
            int el2 = it.next();
            int el3 = it.next();
  
            // Check if their difference is same
            if ((el2 - el1) == (el3 - el2))
                return el2 - el1;
            else
                return -1;
        }
  
        // More than 3 unique elements
        return -1;
    }
  
    // Driver code
    public static void main(String[] args) 
    {
        int a[] = {1, 4, 4, 7, 4, 1};
        int n = a.length;
        System.out.println(findMinimumX(a, n));
    }
}
  
// This code is contributed by
// Rajnis09

Python3

# Python 3 program to implement
# the above approach
  
# Function that returns the
# minimum value of X
def findMinimumX(a, n):
      
    # Declare a set
    st = set()
  
    # Iterate in the array element
    # and insert them into the set
    for i in range(n):
        st.add(a[i])
  
    # If unique elements is 1
    if (len(st) == 1):
        return 0
  
    # Unique elements is 2
    if (len(st) == 2):
          
        # Get both el2 and el1
        st = list(st)
        el1 = st[0]
        el2 = st[1]
  
        # Check if they are even
        if ((el2 - el1) % 2 == 0):
            return int((el2 - el1) / 2)
        else:
            return (el2 - el1)
  
    # If there are 3 unique elements
    if (len(st) == 3):
        st = list(st)
          
        # Get three unique elements
        el1 = st[0]
        el2 = st[1]
        el3 = st[2]
  
        # Check if their difference is same
        if ((el2 - el1) == (el3 - el2)):
            return el2 - el1
        else:
            return -1
  
    # More than 3 unique elements
    return -1
  
# Driver code
if __name__ == '__main__':
    a = [1, 4, 4, 7, 4, 1]
    n = len(a)
    print(findMinimumX(a, n))
  
# This code is contributed by
# Surendra_Gangwar

C#

// C# implementation of the approach
using System;
using System.Collections.Generic; 
  
class GFG 
{
      
    // Function that returns the
    // minimum value of X
    static int findMinimumX(int []a, int n)
    {
  
        // Declare a set
        List<int> st = new List<int>();
  
        // Iterate in the array element
        // and insert them into the set
        for (int i = 0; i < n; i++)
            if(!st.Contains(a[i]))
                st.Add(a[i]);
  
        // If unique elements is 1
        if (st.Count == 1)
            return 0;
  
        // Unique elements is 2
        if (st.Count == 2) 
        {
            // Get both el2 and el1
            int el1 = st[0];
            int el2 = st[1];
  
            // Check if they are even
            if ((el2 - el1) % 2 == 0)
                return (el2 - el1) / 2;
            else
                return (el2 - el1);
        }
  
        // If there are 3 unique elements
        if (st.Count == 3) 
        {
            // Get three unique elements
            int el1 = st[0];
            int el2 = st[1];
            int el3 = st[2];
  
            // Check if their difference is same
            if ((el2 - el1) == (el3 - el2))
                return el2 - el1;
            else
                return -1;
        }
  
        // More than 3 unique elements
        return -1;
    }
  
    // Driver code
    public static void Main(String[] args) 
    {
        int []a = {1, 4, 4, 7, 4, 1};
        int n = a.Length;
        Console.WriteLine(findMinimumX(a, n));
    }
} 
      
// This code is contributed by Princi Singh
Producción:

3

Publicación traducida automáticamente

Artículo escrito por Striver y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *