Dada una array arr[] de tamaño N y un número K . La tarea es imprimir el arreglo arr[] después de K operaciones de modo que en cada operación, reemplace cada elemento arr[i] en el arreglo con max – arr[i] donde max es el elemento máximo en el arreglo.
Ejemplos:
Entrada: arr[] = {4, 8, 12, 16}, K = 4
Salida: 0 4 8 12
Explicación:
Para la array dada arr[] = { 4, 8, 12, 16 }. La array se cambia de la siguiente manera para cada operación K:
{ 12, 8, 4, 0 } – K = 1
{ 0, 4, 8, 12 } – K = 2
{ 12, 8, 4, 0 } – K = 3
{ 0, 4, 8, 12 } – K = 4
Entrada: arr[] = {8, 0, 3, 5}, K = 3
Salida: 0 8 5 3
Explicación:
Para la array dada arr[] = { 8 , 0, 3, 5 }. La array se cambia de la siguiente manera para cada operación K:
{ 0, 8, 5, 3 } – K = 1
{ 8, 0, 3, 5 } – K = 2
{ 0, 8, 5, 3 } – K = 3
Enfoque: La idea es observar claramente la array después de cada paso.
- Inicialmente, dado que estamos restando el elemento máximo de la array, podemos estar seguros de que habrá al menos un elemento en la array con valor cero. Esto sucede después del primer paso que es K = 1 . Deje que la array después de este paso sea A[] con el elemento máximo M .
- Después de este primer paso, la array se estanca y los valores cambian alternativamente de su valor A[i] a M – A[i] alternativamente.
- Por ejemplo, tomemos la array arr[] = {4, 8, 12, 16}. En esta array, el valor máximo es 16 y supongamos que K = 4.
- En el primer paso, (es decir) para K = 1 , la array se reduce a {12, 8, 4, 0} . Es decir, cada elemento arr[i] se reemplaza con 16 – arr[i]. Sea este arreglo A[] y el elemento máximo en este arreglo M es 12.
- Después del primer paso, cada elemento en esta array A[i] cambia alternativamente entre A[i] y 12 – A[i] . Es decir, para K = 2 , la array ahora se convierte en {0, 4, 8, 12} .
- De manera similar, para el tercer paso, (es decir) K = 3 , la array nuevamente se convierte en {12, 8, 4, 0}, que es lo mismo que para K = 1 .
- Y para el cuarto paso, (es decir) K = 4 , la array se convierte en {0, 4, 8, 12} que es lo mismo que para K = 2 y así sucesivamente.
Por lo tanto, se puede concluir que solo necesitamos comprobar si K es par o impar:
- Si K es impar : reemplace cada elemento arr[i] con arr[i] – min donde min es el elemento mínimo en la array.
- Si K es par : reemplace cada elemento arr[i] con max – arr[i] donde max es el elemento máximo en la array.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program to print the array
// after K operations
#include <bits/stdc++.h>
using namespace std;
// Function to print the array
// after K operations
void printArray(int A[], int n, int K)
{
// Variables to store the minimum and
// the maximum elements of the array
int minEle = INT_MAX,
maxEle = INT_MIN;
// Loop to find the minimum and the
// maximum elements of the array
for (int i = 0; i < n; i++) {
minEle = min(minEle, A[i]);
maxEle = max(maxEle, A[i]);
}
// If K is not equal to 0
if (K != 0) {
// If K is odd
if (K % 2 == 1) {
// Replace every element with
// max - arr[i]
for (int i = 0; i < n; i++)
A[i] = maxEle - A[i];
}
// If K is even
else {
// Replace every element with
// A[i] - min
for (int i = 0; i < n; i++)
A[i] = A[i] - minEle;
}
}
// Printing the array after K operations
for (int i = 0; i < n; i++)
cout << A[i] << " ";
}
// Driver code
int main()
{
int arr[] = { 4, 8, 12, 16 };
int K = 4;
int N = sizeof(arr) / sizeof(arr[0]);
printArray(arr, N, K);
return 0;
}
Java
// Java program to print the array
// after K operations
import java.io.*;
class GFG {
// Function to print the array
// after K operations
static void printArray(int[] A, int n, int K)
{
// Variables to store the minimum and
// the maximum elements of the array
int minEle = Integer.MAX_VALUE,
maxEle = Integer.MAX_VALUE;
// Loop to find the minimum and the
// maximum elements of the array
for (int i = 0; i < n; i++) {
minEle = Math.min(minEle, A[i]);
maxEle = Math.max(maxEle, A[i]);
}
// If K is not equal to 0
if (K != 0) {
// If K is odd
if (K % 2 == 1) {
// Replace every element with
// max - arr[i]
for (int i = 0; i < n; i++)
A[i] = maxEle - A[i];
}
// If K is even
else {
// Replace every element with
// A[i] - min
for (int i = 0; i < n; i++)
A[i] = A[i] - minEle;
}
}
// Printing the array after K operations
for (int i = 0; i < n; i++)
System.out.print(A[i] + " ");
}
// Driver Code
public static void main (String[] args)
{
int[] arr = { 4, 8, 12, 16 };
int K = 4;
int N = arr.length;
printArray(arr, N, K);
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python3 program to print the array # after K operations # Function to print the array # after K operations def printArray(A, n, K): # Variables to store the minimum and # the maximum elements of the array minEle = 10**9 maxEle = -10**9 # Loop to find the minimum and the # maximum elements of the array for i in range(n): minEle = min(minEle, A[i]) maxEle = max(maxEle, A[i]) # If K is not equal to 0 if (K != 0): # If K is odd if (K % 2 == 1): # Replace every element with # max - arr[i] for i in range(n): A[i] = maxEle - A[i] # If K is even else: # Replace every element with # A[i] - min for i in range(n): A[i] = A[i] - minEle # Printing the array after K operations for i in A: print(i, end=" ") # Driver code if __name__ == '__main__': arr=[4, 8, 12, 16] K = 4 N = len(arr) printArray(arr, N, K) # This code is contributed by mohit kumar 29
C#
// C# program to print the array
// after K operations
using System;
class GFG{
// Function to print the array
// after K operations
static void printArray(int[] A, int n, int K)
{
// Variables to store the minimum and
// the maximum elements of the array
int minEle = Int32.MaxValue,
maxEle = Int32.MinValue;
// Loop to find the minimum and the
// maximum elements of the array
for (int i = 0; i < n; i++) {
minEle = Math.Min(minEle, A[i]);
maxEle = Math.Max(maxEle, A[i]);
}
// If K is not equal to 0
if (K != 0) {
// If K is odd
if (K % 2 == 1) {
// Replace every element with
// max - arr[i]
for (int i = 0; i < n; i++)
A[i] = maxEle - A[i];
}
// If K is even
else {
// Replace every element with
// A[i] - min
for (int i = 0; i < n; i++)
A[i] = A[i] - minEle;
}
}
// Printing the array after K operations
for (int i = 0; i < n; i++)
Console.Write(A[i] + " ");
}
// Driver code
static public void Main ()
{
int[] arr = { 4, 8, 12, 16 };
int K = 4;
int N = arr.Length;
printArray(arr, N, K);
}
}
// This code is contributed by shubhamsingh10
Javascript
<script>
// Javascript program to print the array
// after K operations
// Function to print the array
// after K operations
function printArray(A, n, K)
{
// Variables to store the minimum and
// the maximum elements of the array
var minEle = 100000000, maxEle = -100000000;
// Loop to find the minimum and the
// maximum elements of the array
for (var i = 0; i < n; i++) {
minEle = Math.min(minEle, A[i]);
maxEle = Math.max(maxEle, A[i]);
}
// If K is not equal to 0
if (K != 0) {
// If K is odd
if (K % 2 == 1) {
// Replace every element with
// max - arr[i]
for (var i = 0; i < n; i++)
A[i] = maxEle - A[i];
}
// If K is even
else {
// Replace every element with
// A[i] - min
for (var i = 0; i < n; i++)
A[i] = A[i] - minEle;
}
}
// Printing the array after K operations
for (var i = 0; i < n; i++)
document.write(A[i] + " ");
}
// Driver code
arr = [ 4, 8, 12, 16 ];
var K = 4;
var N = arr.length;
printArray(arr, N, K);
</script>
Producción:
0 4 8 12
Complejidad de tiempo: O(N) donde N es el tamaño de la array.