- 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