Given an array arr[] of size N, the task is to find another array brr[] of size 2*N such that it is non-decreasing and for each ith from 1 to N arr[i] = brr[i] + brr[2*n – i +1].
Examples:
Input: n = 2, arr[] = { 5, 6 }
Output: 0 1 5 5
Explanation: For i =1, arr[1] = 5, brr[1]+brr[2*2-1+1] = 5, so both are equal, For i =2, arr[2] = 6, brr[2]+brr[2*2-2+1] = 6, so both are equal.Input: n = 3, arr[] = { 2, 1, 2 }
Output: 0 0 1 1 1 2
Approach: Numbers of array brr[] will be restored in pairs (brr[1], brr[2*n]), (brr[2], brr[2*n-1]) and so on. Thus, a certain limit can be there on these values satisfying the above conditions brr[i]+brr[2*N-i-1]==arr[i]. Let l be minimal possible and r be the maximum possible in the answer. Initially, l=0, r=10^18 and they are updated with l=brr[i], r=brr[2*n-i-1]. Follow the steps below to solve the problem:
- Initialize the variables l as 0 and r as INF64.
- Multiply the value of N by 2 to keep the count of the size of the second array.
- Define a function brute(ind, l, r) where ind is the index of the array for which values are to be filled, l and r are the range of the values. Call this function recursively to compute the values for each pair in the second array brr[].
- In the function brute(ind, l, r)
- Define the base case i.e, when the value of ind becomes equal to the size of the first array arr[].
- If yes, then print the elements of the second array brr[] and exit the function.
- Else, iterate in the range [l, arr[ind]/2] and perform the following steps.
- If the value of arr[ind]-i is less than r, then set the value of brr[ind] to i and brr[n-ind-1] to arr[ind]-i.
- Set the value of l to i and r to arr[ind]-i as the updated values of l and r.
- Call the same function recursively brute(ind+1, l, r) for the next index.
Below is the implementation of the above approach.
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 arrayvoid 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 Codeint main(){ n = 2; n *= 2; arr[0] = 5; arr[1] = 6; brute(0, 0, INF64); return 0;} |
Java
// Java program for the above approachimport 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 arraystatic 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 codepublic 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 + 13n = 0arr = [0 for i in range(N)]brr = [0 for i in range(N)]import sys# Function to find the possible# output arraydef 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 Codeif __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 approachusing 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 arraystatic 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 Codepublic 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> |
Output
0 1 5 5
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
