Dada una array A[] de tamaño N/2 , la tarea es construir la array B[] de tamaño N tal que:
- B[] se clasifica en orden no decreciente.
- A[i] = B[i] + B[n – i + 1].
Nota: La array A[] se da de tal manera que la respuesta siempre es posible.
Ejemplos:
Entrada: A[] = {3, 4}
Salida: 0 1 3 3
Entrada: A[] = {4, 1}
Salida: 0 0 1 4
Enfoque: Vamos a presentar el siguiente enfoque codicioso. Los números se restaurarán en pares (B[0], B[n – 1]) , (B[1], B[n – 2]) y así sucesivamente. Por lo tanto, podemos tener algunos límites en los valores del par actual (satisfaciendo los criterios sobre el resultado ordenado).
Inicialmente, l = 0 y r = 10 9 , se actualizan con l = a[i] y r = a[n – i + 1] . Sea l el mínimo posible en la respuesta. Tome a[i] = max(l, b[i] – r) y r = b[i] – l , de esa manera l fue elegido de tal manera que tanto l como restán dentro de las restricciones y l es también mínimo posible.
Si l fuera mayor que moveríamos tanto el límite l hacia arriba como el límite r hacia abajo, dejando menos libertad para elecciones posteriores.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Utility function to print
// the contents of the array
void printArr(int b[], int n)
{
for (int i = 0; i < n; i++)
cout << b[i] << " ";
}
// Function to build array B[]
void ModifiedArray(int a[], int n)
{
// Lower and upper limits
int l = 0, r = INT_MAX;
// To store the required array
int b[n] = { 0 };
// Apply greedy approach
for (int i = 0; i < n / 2; i++) {
b[i] = max(l, a[i] - r);
b[n - i - 1] = a[i] - b[i];
l = b[i];
r = b[n - i - 1];
}
// Print the built array b[]
printArr(b, n);
}
// Driver code
int main()
{
int a[] = { 5, 6 };
int n = sizeof(a) / sizeof(a[0]);
ModifiedArray(a, 2 * n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class solution
{
// Utility function to print
// the contents of the array
void printArr(int b[], int n)
{
for (int i = 0; i < n; i++)
{
System.out.print(" " + b[i] + " ");
}
}
// Function to build array B[]
void ModifiedArray(int a[], int n)
{
// Lower and upper limits
int l = 0, r = Integer.MAX_VALUE;
// To store the required array
int[] b = new int[n];
// Apply greedy approach
for (int i = 0; i < n / 2; i++) {
b[i] = Math.max(l, a[i] - r);
b[n - i - 1] = a[i] - b[i];
l = b[i];
r = b[n - i - 1];
}
// Print the built array b[]
printArr(b, n);
}
// Driver code
public static void main(String args[])
{
int a[] = { 5, 6 };
int n = a.length ;
solution s=new solution();
s.ModifiedArray(a, 2 * n);
}
}
//This code is contributed by Shivi_Aggarwal
Python3
# Python 3 implementation of the approach import sys # Utility function to print the # contents of the array def printArr(b, n): for i in range(0, n, 1): print(b[i], end = " ") # Function to build array B[] def ModifiedArray(a, n): # Lower and upper limits l = 0 r = sys.maxsize # To store the required array b = [0 for i in range(n)] # Apply greedy approach for i in range(0, int(n / 2), 1): b[i] = max(l, a[i] - r) b[n - i - 1] = a[i] - b[i] l = b[i] r = b[n - i - 1] # Print the built array b[] printArr(b, n) # Driver code if __name__ == '__main__': a = [5, 6] n = len(a) ModifiedArray(a, 2 * n) # This code is contributed by # Shashank_Sharma
C#
// C# implementation of the approach
using System;
public class GFG{
// Utility function to print
// the contents of the array
static void printArr(int []b, int n)
{
for (int i = 0; i < n; i++)
{
Console.Write(" " + b[i] + " ");
}
}
// Function to build array B[]
static void ModifiedArray(int []a, int n)
{
// Lower and upper limits
int l = 0, r = int.MaxValue;
// To store the required array
int[] b = new int[n];
// Apply greedy approach
for (int i = 0; i < n / 2; i++) {
b[i] = Math.Max(l, a[i] - r);
b[n - i - 1] = a[i] - b[i];
l = b[i];
r = b[n - i - 1];
}
// Print the built array b[]
printArr(b, n);
}
// Driver code
static public void Main (){
int []a = { 5, 6 };
int n = a.Length;
ModifiedArray(a, 2 * n);
}
}
// This code is contributed
// by Sach_Code
PHP
<?php
// PHP implementation of the approach
// Utility function to print the
// contents of the array
function printArr($b, $n)
{
for ($i = 0; $i < $n; $i++)
echo $b[$i] . " ";
}
// Function to build array B[]
function ModifiedArray($a, $n)
{
// Lower and upper limits
$l = 0; $r = PHP_INT_MAX;
// To store the required array
$b = array(0);
// Apply greedy approach
for ($i = 0; $i < $n / 2; $i++)
{
$b[$i] = max($l, $a[$i] - $r);
$b[$n - $i - 1] = $a[$i] - $b[$i];
$l = $b[$i];
$r = $b[$n - $i - 1];
}
// Print the built array b[]
printArr($b, $n);
}
// Driver code
$a = array( 5, 6 );
$n = sizeof($a);
ModifiedArray($a, 2 * $n);
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// Javascript program of the above approach
// Utility function to print
// the contents of the array
function printArr(b, n)
{
for (let i = 0; i < n; i++)
{
document.write(" " + b[i] + " ");
}
}
// Function to build array B[]
function ModifiedArray(a, n)
{
// Lower and upper limits
let l = 0, r = Number.MAX_VALUE;
// To store the required array
let b = Array(n).fill(0);
// Apply greedy approach
for (let i = 0; i < n / 2; i++) {
b[i] = Math.max(l, a[i] - r);
b[n - i - 1] = a[i] - b[i];
l = b[i];
r = b[n - i - 1];
}
// Print the built array b[]
printArr(b, n);
}
// Driver code
let a = [ 5, 6 ];
let n = a.length ;
ModifiedArray(a, 2 * n);
</script>
0 1 5 5
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA