Dada una array arr[] de tamaño N, la tarea es encontrar otra array brr[] de tamaño 2*N tal que no sea decreciente y para cada i th de 1 a N arr[i] = brr[i] + brr[2*n – i +1].
Ejemplos:
Entrada: n = 2, arr[] = { 5, 6 }
Salida: 0 1 5 5
Explicación: Para i =1, arr[1] = 5, brr[1]+brr[2*2-1+1] = 5, entonces ambos son iguales, For i =2, arr[2] = 6, brr[2]+brr[2*2-2+1] = 6, entonces ambos son iguales.Entrada: n = 3, arr[] = { 2, 1, 2 }
Salida: 0 0 1 1 1 2
Enfoque: los números de la array brr[] se restaurarán en pares (brr[1], brr[2*n]), (brr[2], brr[2*n-1]) y así sucesivamente. Por lo tanto, puede haber un cierto límite en estos valores que satisfagan las condiciones anteriores brr[i]+brr[2*Ni-1]==arr[i]. Sea l el mínimo posible y r el máximo posible en la respuesta. Inicialmente, l=0, r=10^18 y se actualizan con l=brr[i] , r=brr[2*ni-1] . Siga los pasos a continuación para resolver el problema:
- Inicialice las variables l como 0 yr como INF64 .
- Multiplique el valor de N por 2 para llevar la cuenta del tamaño de la segunda array .
- Defina una función bruta (ind, l, r) donde ind es el índice de la array para la cual se deben completar los valores, l y r son el rango de los valores. Llame a esta función recursivamente para calcular los valores de cada par en la segunda array brr[].
- En la función brute(ind, l, r)
- Defina el caso base , es decir, cuando el valor de ind sea igual al tamaño de la primera array arr[].
- En caso afirmativo, imprima los elementos de la segunda array brr[] y salga de la función .
- De lo contrario, itere en el rango [l, arr[ind]/2] y realice los siguientes pasos.
- Si el valor de arr[ind]-i es menor que r, establezca el valor de brr[ind] en i y brr[n-ind-1] en arr[ind]-i.
- Establezca el valor de l a i y r a arr[ind]-i como los valores actualizados de l y r.
- Llame a la misma función recursivamente bruta (ind+1, l, r) para el siguiente índice.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach.
#include <bits/stdc++.h>
using namespace std;
const long long INF64 = 1000000000000000000ll;
const int N = 200 * 1000 + 13;
int n;
long long arr[N], brr[N];
// Function to find the possible
// output array
void brute(int ind, long long l, long long r)
{
// Base case for the recursion
if (ind == n / 2) {
// If ind becomes half of the size
// then print the array.
for (int i = 0; i < int(n); i++)
printf("%lld ", brr[i]);
puts("");
// Exit the function.
exit(0);
}
// Iterate in the range.
for (long long i = l; i <= arr[ind] / 2; ++i)
if (arr[ind] - i <= r) {
// Put the values in the respective
// indices.
brr[ind] = i;
brr[n - ind - 1] = arr[ind] - i;
// Call the function to find values for
// other indices.
brute(ind + 1, i, arr[ind] - i);
}
}
// Driver Code
int main()
{
n = 2;
n *= 2;
arr[0] = 5;
arr[1] = 6;
brute(0, 0, INF64);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
static int INF64 = (int)1e10;
static int N = 200 * 1000 + 13;
static int n;
static int arr[] = new int[N];
static int brr[] = new int[N];
// Function to find the possible
// output array
static void brute(int ind, int l, int r)
{
// Base case for the recursion
if (ind == n / 2)
{
// If ind becomes half of the size
// then print the array.
for(int i = 0; i < (int)n; i++)
System.out.print(brr[i] + " ");
// Exit the function.
System.exit(0);
}
// Iterate in the range.
for(int i = l; i <= arr[ind] / 2; ++i)
if (arr[ind] - i <= r)
{
// Put the values in the respective
// indices.
brr[ind] = i;
brr[n - ind - 1] = arr[ind] - i;
// Call the function to find values for
// other indices.
brute(ind + 1, i, arr[ind] - i);
}
}
// Driver code
public static void main(String[] args)
{
n = 2;
n *= 2;
arr[0] = 5;
arr[1] = 6;
brute(0, 0, INF64);
}
}
// This code is contributed by sanjoy_62
Python3
# Python 3 program for the above approach. N = 200 * 1000 + 13 n = 0 arr = [0 for i in range(N)] brr = [0 for i in range(N)] import sys # Function to find the possible # output array def brute(ind, l, r): # Base case for the recursion if (ind == n / 2): # If ind becomes half of the size # then print the array. for i in range(n): print(brr[i],end = " ") # Exit the function. sys.exit() # Iterate in the range. for i in range(l,arr[ind] // 2 +1,1): if (arr[ind] - i <= r): # Put the values in the respective # indices. brr[ind] = i brr[n - ind - 1] = arr[ind] - i # Call the function to find values for # other indices. brute(ind + 1, i, arr[ind] - i) # Driver Code if __name__ == '__main__': n = 2 n *= 2 arr[0] = 5 arr[1] = 6 INF64 = 1000000000000000000 brute(0, 0, INF64) # This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
static int INF64 = (int)1e8;
static int N = 200 * 1000 + 13;
static int n;
static int[] arr = new int[N];
static int[] brr = new int[N];
// Function to find the possible
// output array
static void brute(int ind, int l, int r)
{
// Base case for the recursion
if (ind == n / 2)
{
// If ind becomes half of the size
// then print the array.
for(int i = 0; i < (int)n; i++)
Console.Write(brr[i] + " ");
// Exit the function.
System.Environment.Exit(0);
}
// Iterate in the range.
for(int i = l; i <= arr[ind] / 2; ++i)
if (arr[ind] - i <= r)
{
// Put the values in the respective
// indices.
brr[ind] = i;
brr[n - ind - 1] = arr[ind] - i;
// Call the function to find values for
// other indices.
brute(ind + 1, i, arr[ind] - i);
}
}
// Driver Code
public static void Main()
{
n = 2;
n *= 2;
arr[0] = 5;
arr[1] = 6;
brute(0, 0, INF64);
}
}
// This code is contributed by target_2.
Javascript
<script>
// JavaScript program for the above approach
const INF64 = 1000000000000000000;
const N = 200 * 1000 + 13;
let n;
let arr = Array(N);
let brr = Array(N);
// Function to find the possible
// output array
function brute(ind, l, r)
{
// Base case for the recursion
if (ind == n / 2)
{
// If ind becomes half of the size
// then print the array.
for (let i = 0; i < n; i++)
document.write(brr[i]+" ");
// Exit the function.
exit(0);
}
// Iterate in the range.
for (let i = l; i <= arr[ind] / 2; ++i)
if (arr[ind] - i <= r)
{
// Put the values in the respective
// indices.
brr[ind] = i;
brr[n - ind - 1] = arr[ind] - i;
// Call the function to find values for
// other indices.
brute(ind + 1, i, arr[ind] - i);
}
}
// Driver Code
n = 2;
n *= 2;
arr[0] = 5;
arr[1] = 6;
brute(0, 0, INF64);
// This code is contributed by Potta Lokesh
</script>
Producción
0 1 5 5
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ujjwalgoel1103 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA