Dada una array arr[] . La array contiene números de 0 a N-1 únicamente, donde N es el tamaño de arr[] . La tarea es modificar la array de tal manera que para cada i de 0≤i<N , arr[i] = arr[ (arr[i-1] + arr[i+1]) / 2 ]
Hay algunas excepciones:
- Para el primer elemento de la array, arr[i-1] = 0 ; porque el índice anterior no existe.
- Para el último elemento de la array, arr[i+1] = 0 ; porque el siguiente índice no existe.
Ejemplos:
Entrada: arr[]= {3, 2, 1, 4, 1, 8, 6, 8, 7}
Salida: [2, 1, 4, 2, 6, 4, 7, 6, 1]
Explicación: Los siguientes son las operaciones realizadas para llegar a la salida deseada.
Para el índice 0, arr[i-1]=0 y arr[i+1]=2, arr[0]= arr[(0+2)/2] = arr[1] = 2 Para el índice 3, arr
[ i-1]=1 y array[i+1]=1, array[3]= array[(1+1)/2] = array[1] = 2Entrada: arr[]= {2, 5, 3, 4, 0, 1}
Salida: [3, 3, 0, 5, 3, 2]
Explicación: Las siguientes son las operaciones realizadas para llegar a la salida deseada.
Para el índice 1, arr[i-1]=2 y arr[i+1]=3, arr[1]= arr[(2+3)/2] = arr[2] = 3 Para el índice 4, arr
[ i-1]=4 y array[i+1]=1, array[4]= array[(4+1)/2] = array[2] = 3
Enfoque ingenuo: la forma más sencilla es crear una nueva array y calcular los valores para cada índice utilizando la array dada, pero esto requerirá espacio adicional. Para cada índice, obtenga los valores de los índices anterior y siguiente y calcule su promedio. Este promedio será el índice cuyo valor se debe copiar en el índice elegido en la nueva array. Así, se logrará arr[i] = arr[ (arr[i-1] + arr[i+1]) / 2 ] .
Complejidad de tiempo: O(N), N es el tamaño de arr[].
Espacio Auxiliar: O(N)
Enfoque eficiente: este enfoque atraviesa la misma array una vez y al final se encontrará la array deseada. Realice un seguimiento del elemento de índice anterior, de modo que incluso si se modifica su valor, es posible calcular el valor anterior. En este caso solo se utiliza el espacio O(1 ), el de la variable temporal para almacenar el valor del elemento anterior.
¿Cómo lograr esto?
Considere dos números x e y , ambos son menores que N. El objetivo es actualizar el valor de x (x = y) de forma que no se pierda el valor antiguo (x=x) . Básicamente, solo mantenga dos valores de x en la misma variable. Para ello Primero, incrementa el valor x por el factor y*N . La x actualizada se convierte en x+y*N . El valor anterior de x se puede obtener tomando mod de Valor actualizado; (x+y*N % N) . El nuevo valor de x se puede obtener tomando el cociente de dividir por N, (x+y*N/N) . Siga los pasos a continuación para resolver el problema dado.
- Itere la array arr[] de izquierda a derecha.
- Para cada índice, incremente el elemento en arr[(arr[i-1]+arr[i+1])/2] * N .
- Para obtener el elemento anterior del i-ésimo, encuentre el módulo con N , es decir, arr[i-1]%N .
- Para obtener el siguiente del i-ésimo elemento, encuentre el cociente con N , es decir, arr[i+1]/N .
- De nuevo, atraviesa la array de principio a fin.
- Imprime el i-ésimo elemento después de dividir el i-ésimo elemento por N , es decir, array[i]/N .
A continuación se muestra la implementación del enfoque anterior.
C++
// Program to modify the given array
// as per given constraint.
#include <iostream>
using namespace std;
// Function to find the previous val
int FindPrev(int i, int a, int n)
{
if (i == 0)
return 0;
else
return a % n;
}
// Function to find the next value
int FindNext(int i, int a, int n)
{
if (i == n - 1)
return 0;
else
return a;
}
// The function to rearrange an array
// in-place so that arr[i] becomes
// arr[(arr[i-1]+arr[i+1])/2].
void ModifyTheArray(int arr[], int n)
{
int new_ind, new_ind_val, next, prev;
// Traverse the array arr[]
for (int i = 0; i < n; i++) {
prev = FindPrev(i, arr[i - 1], n);
next = FindNext(i, arr[i + 1], n);
new_ind = (prev + next) / 2;
new_ind_val = arr[new_ind] % n;
arr[i] = arr[i] + n * new_ind_val;
}
for (int i = 0; i < n; i++)
arr[i] /= n;
}
// A utility function to display the array of size n
void DisplayArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
// Driver Code
int main()
{
int arr[] = { 3, 2, 1, 4, 1, 8, 6, 8, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << "Given array is=> \n";
DisplayArray(arr, N);
ModifyTheArray(arr, N);
cout << "Modified array is=> \n";
DisplayArray(arr, N);
return 0;
}
Java
// Java Program to modify the given array
// as per given constraint.
import java.util.*;
public class GFG
{
// Function to find the previous val
static int FindPrev(int i, int a, int n)
{
if (i == 0)
return 0;
else
return a % n;
}
// Function to find the next value
static int FindNext(int i, int a, int n)
{
if (i == n - 1)
return 0;
else
return a;
}
// The function to rearrange an array
// in-place so that arr[i] becomes
// arr[(arr[i-1]+arr[i+1])/2].
static void ModifyTheArray(int arr[], int n)
{
int new_ind, new_ind_val, next, prev;
// Traverse the array arr[]
for (int i = 0; i < n; i++) {
if(i - 1 >= 0 ){
prev = FindPrev(i, arr[i - 1], n);
}
else{
prev = 0;
}
if(i + 1 < n){
next = FindNext(i, arr[i + 1], n);
}
else{
next = 0;
}
new_ind = (prev + next) / 2;
new_ind_val = arr[new_ind] % n;
arr[i] = arr[i] + n * new_ind_val;
}
for (int i = 0; i < n; i++)
arr[i] /= n;
}
// A utility function to display the array of size n
static void DisplayArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver code
public static void main(String args[])
{
int arr[] = { 3, 2, 1, 4, 1, 8, 6, 8, 7 };
int N = arr.length;
System.out.println("Given array is=>");
DisplayArray(arr, N);
ModifyTheArray(arr, N);
System.out.println("Modified array is=>");
DisplayArray(arr, N);
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# python3 Program to modify the given array
# as per given constraint.
# Function to find the previous val
def FindPrev(i, a, n):
if (i == 0):
return 0
else:
return a % n
# Function to find the next value
def FindNext(i, a, n):
if (i == n - 1):
return 0
else:
return a
# The function to rearrange an array
# in-place so that arr[i] becomes
# arr[(arr[i-1]+arr[i+1])/2].
def ModifyTheArray(arr, n):
# Traverse the array arr[]
for i in range(0, n):
prev = FindPrev(i, arr[i - 1], n)
next = FindNext(i, arr[i + 1], n) if i + 1 < n else 0
new_ind = (prev + next) // 2
new_ind_val = arr[new_ind] % n
arr[i] = arr[i] + n * new_ind_val
for i in range(0, n):
arr[i] //= n
# A utility function to display the array of size n
def DisplayArray(arr, n):
for i in range(0, n):
print(arr[i], end=" ")
print()
# Driver Code
if __name__ == "__main__":
arr = [3, 2, 1, 4, 1, 8, 6, 8, 7]
N = len(arr)
print("Given array is=> ")
DisplayArray(arr, N)
ModifyTheArray(arr, N)
print("Modified array is=> ")
DisplayArray(arr, N)
# This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
using System.Collections;
class GFG
{
// Function to find the previous val
static int FindPrev(int i, int a, int n)
{
if (i == 0)
return 0;
else
return a % n;
}
// Function to find the next value
static int FindNext(int i, int a, int n)
{
if (i == n - 1)
return 0;
else
return a;
}
// The function to rearrange an array
// in-place so that arr[i] becomes
// arr[(arr[i-1]+arr[i+1])/2].
static void ModifyTheArray(int []arr, int n)
{
int new_ind, new_ind_val, next, prev;
// Traverse the array arr[]
for (int i = 0; i < n; i++) {
if(i - 1 >= 0 ){
prev = FindPrev(i, arr[i - 1], n);
}
else{
prev = 0;
}
if(i + 1 < n){
next = FindNext(i, arr[i + 1], n);
}
else{
next = 0;
}
new_ind = (prev + next) / 2;
new_ind_val = arr[new_ind] % n;
arr[i] = arr[i] + n * new_ind_val;
}
for (int i = 0; i < n; i++)
arr[i] /= n;
}
// A utility function to display the array of size n
static void DisplayArray(int []arr, int n)
{
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
Console.WriteLine();
}
// Driver code
public static void Main()
{
int []arr = { 3, 2, 1, 4, 1, 8, 6, 8, 7 };
int N = arr.Length;
Console.WriteLine("Given array is=>");
DisplayArray(arr, N);
ModifyTheArray(arr, N);
Console.WriteLine("Modified array is=>");
DisplayArray(arr, N);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript program to modify the given array
// as per given constraint.
// Function to find the previous val
function FindPrev(i, a, n)
{
if (i == 0)
return 0;
else
return a % n;
}
// Function to find the next value
function FindNext(i, a, n)
{
if (i == n - 1)
return 0;
else
return a;
}
// The function to rearrange an array
// in-place so that arr[i] becomes
// arr[(arr[i-1]+arr[i+1])/2].
function ModifyTheArray(arr, n)
{
let new_ind, new_ind_val, next, prev;
// Traverse the array arr[]
for(let i = 0; i < n; i++)
{
prev = FindPrev(i, arr[i - 1], n);
next = FindNext(i, arr[i + 1], n);
new_ind = Math.floor((prev + next) / 2);
new_ind_val = arr[new_ind] % n;
arr[i] = arr[i] + n * new_ind_val;
}
for(let i = 0; i < n; i++)
arr[i] = Math.floor(arr[i] / n);
}
// A utility function to display the array of size n
function DisplayArray(arr, n)
{
for(let i = 0; i < n; i++)
document.write(arr[i] + " ")
document.write('<br')
}
// Driver Code
let arr = [ 3, 2, 1, 4, 1, 8, 6, 8, 7 ];
let N = arr.length;
document.write("Given array is=> " + "<br>");
DisplayArray(arr, N);
ModifyTheArray(arr, N);
document.write("Modified array is=> " + "<br>");
DisplayArray(arr, N);
// This code is contributed by Potta Lokesh
</script>
Given array is=> 3 2 1 4 1 8 6 8 7 Modified array is=> 2 1 4 2 6 4 7 6 1
Complejidad de tiempo : O(N), donde N es el tamaño de arr[] ya que estamos usando un bucle para atravesar N veces.
Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.
Publicación traducida automáticamente
Artículo escrito por pintusaini y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA