El entero positivo más pequeño K tal que todos los elementos de la array se pueden igualar incrementando o decrementando K como máximo

Posted on by Rudeus Greyrat

Dada una array arr[] de tamaño N , la tarea es encontrar el entero positivo más pequeño K tal que incrementar o disminuir cada elemento de la array en K como máximo una vez hace que todos los elementos sean iguales. Si no es posible hacer que todos los elementos de la array sean iguales, imprima -1 .

Ejemplos:

Entrada: arr[] = { 5, 7, 9 }
Salida: 2
Explicación: 
Incrementar el valor de arr[0] por K(= 2) modifica arr[] a { 7, 7, 9 }. 
Decrementar el valor de arr[2] por K(= 2) modifica arr[] a { 7, 7, 7 }

Entrada: arr[] = {1, 3, 9}, N = 3
Salida: -1

 

Enfoque: siga los pasos a continuación para resolver el problema:

  • Inicialice un conjunto para almacenar todos los elementos distintos presentes en la array .
  • Cuente los distintos elementos en la array , que es igual al tamaño del Conjunto , digamos M.
  • Si M > 3 , imprima -1 .
  • Si M = 3 , compruebe si la diferencia entre el elemento más grande y el segundo más grande del Conjunto es igual a la diferencia entre el segundo y el tercer elemento más grande del Conjunto o no. Si se encuentra que es cierto, imprima la diferencia. De lo contrario, imprima -1 .
  • Si M = 2 , compruebe si la diferencia entre el elemento más grande y el segundo más grande del conjunto es par o no. Si se encuentra que es cierto, imprima la mitad de su diferencia. De lo contrario, imprima la diferencia.
  • Si M <= 1 , imprima 0 .

A continuación se muestra la implementación de la solución anterior:

C++

// C++ program for the above approach
#include <iostream>
#include <set>
using namespace std;
 
// Function to find smallest integer K such that
// incrementing or decrementing each element by
// K at most once makes all elements equal
void findMinKToMakeAllEqual(int N, int A[])
{
 
    // Store distinct
    // array elements
    set<int> B;
 
    // Traverse the array, A[]
    for (int i = 0; i < N; i++)
        B.insert(A[i]);
 
    // Count elements into the set
    int M = B.size();
 
    // Iterator to store first
    // element of B
    set<int>::iterator itr = B.begin();
 
    // If M is greater than 3
    if (M > 3)
        printf("-1");
 
    // If M is equal to 3
    else if (M == 3) {
 
        // Stores the first
        // smallest element
        int B_1 = *itr;
 
        // Stores the second
        // smallest element
        int B_2 = *(++itr);
 
        // Stores the largest element
        int B_3 = *(++itr);
 
        // IF difference between B_2 and B_1
        // is equal to B_3 and B_2
        if (B_2 - B_1 == B_3 - B_2)
            printf("%d", B_2 - B_1);
        else
            printf("-1");
    }
 
    // If M is equal to 2
    else if (M == 2) {
 
        // Stores the smallest element
        int B_1 = *itr;
 
        // Stores the largest element
        int B_2 = *(++itr);
 
        // If difference is an even
        if ((B_2 - B_1) % 2 == 0)
            printf("%d", (B_2 - B_1) / 2);
        else
            printf("%d", B_2 - B_1);
    }
 
    // If M is equal to 1
    else
        printf("%d", 0);
}
 
// Driver Code
int main()
{
 
    // Given array
    int A[] = { 1, 3, 5, 1 };
 
    // Given size
    int N = sizeof(A) / sizeof(A[0]);
 
    // Print the required smallest integer
    findMinKToMakeAllEqual(N, A);
}

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
     
    // Function to find smallest integer K such that
    // incrementing or decrementing each element by
    // K at most once makes all elements equal
    static void findMinKToMakeAllEqual(int N, int A[])
    {
       
        // Store distinct
        // array elements
        Set<Integer> B = new HashSet<Integer>();
       
        // Traverse the array, A[]
        for (int i = 0; i < N; i++)
        {
            B.add(A[i]);
        }
         
        ArrayList<Integer> b = new ArrayList<Integer>(B);
       
        // Count elements into the set
        int M = b.size();
        int i = 0;
       
        // If M is greater than 3
        if (M > 3)
        {    System.out.print("-1");}
         
         
        // If M is equal to 3
        else if (M == 3)
        {
           
            // Stores the first
            // smallest element
            int B_1 = b.get(i++);
             
            // Stores the second
            // smallest element
            int B_2 =  b.get(i++);
             
            // Stores the largest element
            int B_3 = b.get(i++);
             
            // IF difference between B_2 and B_1
            // is equal to B_3 and B_2
            if (B_2 - B_1 == B_3 - B_2)
            {
                System.out.print(B_2 - B_1);
            }
            else
            {
                System.out.print("-1");
            }
             
             
        }
         
        // If M is equal to 2
        else if (M == 2)
        {
           
            // Stores the smallest element
            int B_1 = b.get(i++);
             
            // Stores the largest element
            int B_2 = b.get(i++);
             
            // If difference is an even
            if ((B_2 - B_1) % 2 == 0)
            {
                System.out.print((B_2 - B_1) / 2);
            }
             
            else
            {
                System.out.print(B_2 - B_1);
            }
        }
        // If M is equal to 1
        else
        {
            System.out.print(0);
        }
    }
     
  // Driver code
    public static void main (String[] args)
    {
         
        // Given array
        int A[] = { 1, 3, 5, 1 };
  
        // Given size
        int N = A.length;
         
         
        // Print the required smallest integer
        findMinKToMakeAllEqual(N, A);
    }
}
 
// This code is contributed by rag2127

Python3

# Python3 program for the above approach
 
# Function to find smallest integer K such
# that incrementing or decrementing each
# element by K at most once makes all
# elements equal
def findMinKToMakeAllEqual(N, A):
     
    # Store distinct
    # array elements
    B = {}
     
    # Traverse the array, A[]
    for i in range(N):
        B[A[i]] = 1
         
    # Count elements into the set
    M = len(B)
     
    # Iterator to store first
    # element of B
    itr, i = list(B.keys()), 0
     
    # If M is greater than 3
    if (M > 3):
        print("-1")
 
    # If M is equal to 3
    elif (M == 3):
         
        # Stores the first
        # smallest element
        B_1, i = itr[i], i + 1
         
        # Stores the second
        # smallest element
        B_2, i = itr[i], i + 1
 
        # Stores the largest element
        B_3, i = itr[i], i + 1
 
        # IF difference between B_2 and B_1
        # is equal to B_3 and B_2
        if (B_2 - B_1 == B_3 - B_2):
            print(B_2 - B_1)
        else:
            print("-1")
 
    # If M is equal to 2
    elif (M == 2):
         
        # Stores the smallest element
        B_1, i = itr[i], i + 1
         
        # Stores the largest element
        B_2, i = itr[i], i + 1
         
        # If difference is an even
        if ((B_2 - B_1) % 2 == 0):
            print((B_2 - B_1) // 2)
        else:
            print(B_2 - B_1)
 
    # If M is equal to 1
    else:
        print(0)
 
# Driver Code
if __name__ == '__main__':
     
    # Given array
    A = [ 1, 3, 5, 1 ]
     
    # Given size
    N = len(A)
 
    # Print the required smallest integer
    findMinKToMakeAllEqual(N, A)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
 
  // Function to find smallest integer K such that
  // incrementing or decrementing each element by
  // K at most once makes all elements equal
  static void findMinKToMakeAllEqual(int N, int[] A)
  {
 
    // Store distinct
    // array elements
    var B = new HashSet<int>();
 
    // Traverse the array, A[]
    for (int i = 0; i < N; i++) {
      B.Add(A[i]);
    }
 
    List<int> b = new List<int>(B);
 
    // Count elements into the set
    int M = b.Count;
    int j = 0;
 
    // If M is greater than 3
    if (M > 3) {
      Console.Write("-1");
    }
 
    // If M is equal to 3
    else if (M == 3) {
 
      // Stores the first
      // smallest element
      int B_1 = b[j++];
 
      // Stores the second
      // smallest element
      int B_2 = b[j++];
 
      // Stores the largest element
      int B_3 = b[j++];
 
      // IF difference between B_2 and B_1
      // is equal to B_3 and B_2
      if (B_2 - B_1 == B_3 - B_2) {
        Console.Write(B_2 - B_1);
      }
      else {
        Console.Write("-1");
      }
    }
 
    // If M is equal to 2
    else if (M == 2) {
 
      // Stores the smallest element
      int B_1 = b[j++];
 
      // Stores the largest element
      int B_2 = b[j++];
 
      // If difference is an even
      if ((B_2 - B_1) % 2 == 0) {
        Console.Write((B_2 - B_1) / 2);
      }
 
      else {
        Console.Write(B_2 - B_1);
      }
    }
    // If M is equal to 1
    else {
      Console.Write(0);
    }
  }
 
  // Driver code
  public static void Main(string[] args)
  {
 
    // Given array
    int[] A = { 1, 3, 5, 1 };
 
    // Given size
    int N = A.Length;
 
    // Print the required smallest integer
    findMinKToMakeAllEqual(N, A);
  }
}
 
// This code is contributed by chitranayal.

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to find smallest integer K such that
// incrementing or decrementing each element by
// K at most once makes all elements equal
function findMinKToMakeAllEqual(N, A)
{
     
    // Store distinct
    // array elements
    var B = new Set();
 
    // Traverse the array, A[]
    for(var i = 0; i < N; i++)
        B.add(A[i]);
 
    // Count elements into the set
    var M = B.size;
 
    // Iterator to store first
    // element of B
    var itr = [...B].sort((a, b) => a - b);
 
    // If M is greater than 3
    if (M > 3)
        document.write("-1");
 
    // If M is equal to 3
    else if (M == 3)
    {
         
        // Stores the first
        // smallest element
        var B_1 = itr[0];
 
        // Stores the second
        // smallest element
        var B_2 = itr[1];
 
        // Stores the largest element
        var B_3 = itr[2];
 
        // IF difference between B_2 and B_1
        // is equal to B_3 and B_2
        if (B_2 - B_1 == B_3 - B_2)
            document.write(B_2 - B_1);
        else
            document.write("-1");
    }
 
    // If M is equal to 2
    else if (M == 2)
    {
         
        // Stores the smallest element
        var B_1 = itr[0];
 
        // Stores the largest element
        var B_2 =itr[1];
 
        // If difference is an even
        if ((B_2 - B_1) % 2 == 0)
            document.write(parseInt((B_2 - B_1) / 2));
        else
            document.write(B_2 - B_1);
    }
 
    // If M is equal to 1
    else
        document.write(0);
}
 
// Driver Code
 
// Given array
var A = [ 1, 3, 5, 1 ];
 
// Given size
var N = A.length;
 
// Print the required smallest integer
findMinKToMakeAllEqual(N, A);
 
// This code is contributed by noob2000
 
</script>
Producción: 

2

 

Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por pkjrockzz 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 *