Encuentre la array final después de restar el máximo de todos los elementos K veces

Posted on by Rudeus Greyrat

Dada una array arr[] de N enteros y un entero K, la tarea es realizar las siguientes operaciones con esta array K veces. Las operaciones son las siguientes:

  • Encuentre el elemento máximo (digamos M ) de la array.
  • Ahora reemplace cada elemento con M-arr i . donde 1 ≤ yo ≤ N. 

Ejemplos:

Entrada: N = 6, K = 3, arr[] = {5, 38, 4, 96, 103, 41}
Salida: 98 65 99 7 0 62
Explicación: 
1.ª operación => El elemento de array máximo es 103. Resta 103 de todos los elementos array[] = {98, 65, 99, 7, 0, 62}.
2da operación => El elemento máximo de la array es 99. Resta 99 de todos los elementos. arr[] = {1, 34, 0, 92, 99, 37}
3ra operación => El elemento máximo de la array es 99. Resta 99 de todos los elementos. array[] = {98, 65, 99, 7, 0, 62}. 
Este será el último estado.

Entrada: N = 5, K = 1, arr[] = {8, 4, 3, 10, 15}
Salida: 7 11 12 5 0

 

Enfoque ingenuo: el enfoque simple es realizar las operaciones anteriores K veces. Cada vez que encuentre el elemento máximo en la array y luego actualice todos los elementos con la diferencia del máximo. 

Complejidad temporal: O(N*K). 
Espacio Auxiliar: O(1).

Enfoque eficiente: la solución eficiente a este problema se basa en la siguiente observación:

Si   K es impar, la respuesta final será equivalente a la respuesta después de aplicar la operación solo una vez y si K es par, la array final será equivalente a la array después de aplicar las operaciones solo dos veces.

Esto se puede probar de acuerdo con lo siguiente:

Digamos máximo = M y la array inicial es arr[] .
Después de realizar las operaciones por primera vez:
        => El elemento máximo de arr[] se convierte en 0.
        => Todos los demás elementos son M – arr[i].
        => Digamos que la nueva array es a1[]. Entonces, a1[i] = M – arr[i].

Después de que la operación se realice por segunda vez:
        => Decir que el máximo de a1[] es M1.
        => El elemento máximo de a1[] se convierte en 0.
        => Todos los demás elementos son M1 – a1[i].
        => Digamos que la nueva array es a2[]. Entonces, a2[i] = M1 – a1[i].
        => El máximo de a2[] será M1, porque el 0 presente en a1[] cambia a M1 y todos los demás elementos son menores que M1.

Después de la operación se realiza la tercera vez:
        => El máximo es M1.
        => El máximo cambia a 0.
        => Todos los demás elementos son M1 – a2[i] = M1 – (M1 – a1[i]) = a1[i].
        => Entonces la nueva array es igual a a1[].

Después de que la operación se realice por cuarta vez:
        => Diga que el máximo de la array es M1.
        => El elemento máximo cambia a 0.
        => Todos los demás elementos son M1 – a1[i].
        => Entonces la nueva array es la misma que a2[]

De lo anterior, está claro que los estados alternativos de la array son los mismos.

Siga los pasos a continuación para implementar la observación:

  • Tome una variable max y almacene el elemento máximo de arr .
  • si k es impar
    • Recorra la array y reste cada elemento del elemento máximo.
  • Más
    • Recorra el arr y reste cada elemento del elemento máximo y 
      almacene el elemento máximo en la variable max1 .
    • Recorra nuevamente el arr y reste cada elemento del elemento máximo.
  • Imprime la array final.

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

C++

// C++ code for the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function for converting the array
void find(int n, int k, int arr[])
{
    // Find the maximum element in array
    int max = INT_MIN;
    for (int i = 0; i < n; i++) {
 
        if (arr[i] > max) {
            max = arr[i];
        }
    }
 
    // If k is odd
    if (k % 2 != 0) {
        for (int i = 0; i < n; i++) {
            cout << max - arr[i] << " ";
        }
    }
    // If k is even
    else {
 
        // Subtract the max from every
        // element of array and store
        // the next maximum element in max1
        int max1 = INT_MIN;
        for (int i = 0; i < n; i++) {
            arr[i] = max - arr[i];
            if (arr[i] > max1) {
                max1 = arr[i];
            }
        }
 
        // Print the output
        for (int i = 0; i < n; i++) {
            cout << max1 - arr[i] << " ";
        }
    }
}
 
// Driver code
int main()
{
    int N = 6, K = 3;
    int arr[] = { 5, 38, 4, 96, 103, 41 };
 
    // Function call
    find(N, K, arr);
    return 0;
}

C

// C code for the approach
#include <stdio.h>
#include<limits.h>
 
// Function for converting the array
void find(int n, int k, int arr[])
{
  // Find the maximum element in array
  int max = INT_MIN;
  for (int i = 0; i < n; i++) {
 
    if (arr[i] > max) {
      max = arr[i];
    }
  }
 
  // If k is odd
  if (k % 2 != 0) {
    for (int i = 0; i < n; i++) {
      printf("%d ", max - arr[i]);
    }
  }
  // If k is even
  else {
 
    // Subtract the max from every
    // element of array and store
    // the next maximum element in max1
    int max1 = INT_MIN;
    for (int i = 0; i < n; i++) {
      arr[i] = max - arr[i];
      if (arr[i] > max1) {
        max1 = arr[i];
      }
    }
 
    // Print the output
    for (int i = 0; i < n; i++) {
      printf("%d ", max1 - arr[i]);
    }
  }
}
 
// Driver code
void main()
{
  int N = 6, K = 3;
  int arr[] = { 5, 38, 4, 96, 103, 41 };
 
  // Function call
  find(N, K, arr);
}
 
// This code is contributed by ashishsingh13122000.

Java

// Java code for the approach
import java.io.*;
 
class GFG
{
 
  // Function for converting the array
  public static void find(int n, int k, int arr[])
  {
 
    // Find the maximum element in array
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
 
      if (arr[i] > max) {
        max = arr[i];
      }
    }
 
    // If k is odd
    if (k % 2 != 0) {
      for (int i = 0; i < n; i++) {
        System.out.print((max - arr[i]) + " ");
      }
    }
 
    // If k is even
    else {
 
      // Subtract the max from every
      // element of array and store
      // the next maximum element in max1
      int max1 = Integer.MIN_VALUE;
      for (int i = 0; i < n; i++) {
        arr[i] = max - arr[i];
        if (arr[i] > max1) {
          max1 = arr[i];
        }
      }
 
      // Print the output
      for (int i = 0; i < n; i++) {
        System.out.print((max1 - arr[i]) + " ");
      }
    }
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int N = 6, K = 3;
    int arr[] = { 5, 38, 4, 96, 103, 41 };
 
    // Function call
    find(N, K, arr);
  }
}
 
// This code is contributed by Rohit Pradhan

Python3

# Python code
 
# Function for converting the array
def find(n, k, arr):
   
    # Find the maximum element in array
    max = (-2147483647 - 1)
    for i in range(0, n):
        if (arr[i] > max):
            max = arr[i]
 
    # If k is odd
    if (k % 2 != 0):
        for i in range (0, n):
            print( max - arr[i], end = " ")
    # If k is even
    else:
        max1 = INT_MIN
        for i in range(0,n):
            arr[i] = max - arr[i]
            if (arr[i] > max1):
                max1 = arr[i]
 
        # Print the output
        for i in range(0,n):
            print(max1 - arr[i],end=" ")
 
# Driver code
N = 6
K = 3
arr = [5, 38, 4, 96, 103, 41]
 
# Function call
find(N,K,arr)
 
# This code is contributed by ashishsingh13122000.

C#

// C# code for the approach
using System;
 
class GFG
{
 
  // Function for converting the array
  static void find(int n, int k, int []arr)
  {
 
    // Find the maximum element in array
    int max = Int32.MinValue;
    for (int i = 0; i < n; i++) {
 
      if (arr[i] > max) {
        max = arr[i];
      }
    }
 
    // If k is odd
    if (k % 2 != 0) {
      for (int i = 0; i < n; i++) {
        Console.Write((max - arr[i]) + " ");
      }
    }
 
    // If k is even
    else {
 
      // Subtract the max from every
      // element of array and store
      // the next maximum element in max1
      int max1 = Int32.MinValue;
      for (int i = 0; i < n; i++) {
        arr[i] = max - arr[i];
        if (arr[i] > max1) {
          max1 = arr[i];
        }
      }
 
      // Print the output
      for (int i = 0; i < n; i++) {
        Console.Write((max1 - arr[i]) + " ");
      }
    }
  }
 
  // Driver Code
  public static void Main()
  {
    int N = 6, K = 3;
    int []arr = { 5, 38, 4, 96, 103, 41 };
 
    // Function call
    find(N, K, arr);
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
    // JavaScript code for the approach
    const INT_MIN = -2147483648;
 
    // Function for converting the array
    const find = (n, k, arr) => {
     
        // Find the maximum element in array
        let max = INT_MIN;
        for (let i = 0; i < n; i++) {
 
            if (arr[i] > max) {
                max = arr[i];
            }
        }
 
        // If k is odd
        if (k % 2 != 0) {
            for (let i = 0; i < n; i++) {
                document.write(`${max - arr[i]} `);
            }
        }
        // If k is even
        else {
 
            // Subtract the max from every
            // element of array and store
            // the next maximum element in max1
            let max1 = INT_MIN;
            for (let i = 0; i < n; i++) {
                arr[i] = max - arr[i];
                if (arr[i] > max1) {
                    max1 = arr[i];
                }
            }
 
            // Print the output
            for (let i = 0; i < n; i++) {
                document.write(`${max1 - arr[i]} `);
            }
        }
    }
 
    // Driver code
 
    let N = 6, K = 3;
    let arr = [5, 38, 4, 96, 103, 41];
 
    // Function call
    find(N, K, arr);
 
// This code is contributed by rakeshsahni
 
</script>
Producción

98 65 99 7 0 62

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

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