Given an array arr[] of size N that contains the differences between the adjacents elements of an array. The task is to generate all possible arrays such that all the elements of the array lie in the range [L, R].
Examples:
Input: arr[] = {1, -3, 4}, L = 1, R = 6
Output: {3, 4, 1, 5}, {4, 5, 2, 6}
Explanation: These two are the only possible sequences having all the elements in given range.Input: arr[] = {4}, L = 2, R = 5
Output: -1
Explanation: No such sequence is possible
Approach: The solution is based on the concept of recursion. Use recursion in the range of L and R and try all possible cases. If no such sequence is found print -1;
Below is the implementation of the above approach.
C++
// C++ program to implement the approach #include <bits/stdc++.h> using namespace std; // Global variable to note // if any sequence found or not bool flag = false ; // Function to find a sequence void find( int L, int R, int starting, vector< int >& arr, vector< int >& ans) { if (starting == ans.size() - 1) { flag = true ; for ( auto elements : ans) { cout << elements << " " ; } cout << "\n" ; return ; } // Loop to form the sequence for ( int i = L; i <= R; ++i) { if (starting == -1) { ans[starting + 1] = i; // Recursive call find(L, R, starting + 1, arr, ans); } else { // Check the previous if (i - ans[starting] == arr[starting]) { ans[starting + 1] = i; // Recursive call find(L, R, starting + 1, arr, ans); } } } } // Driver code int main() { vector< int > arr{ 1, -3, 4 }; int L = 1; int R = 6; vector< int > ans(arr.size() + 1); find(L, R, -1, arr, ans); if (!flag) cout << (-1); return 0; } // This code is contributed by rakeshsahni |
Java
// Java program to implement the approach import java.io.*; class GFG { // Global variable to note // if any sequence found or not static boolean flag = false ; // Function to find a sequence static void find( int L, int R, int starting, int arr[], int ans[]) { if (starting == ans.length - 1 ) { flag = true ; for ( int elements : ans) { System.out.print(elements + " " ); } System.out.println(); return ; } // Loop to form the sequence for ( int i = L; i <= R; ++i) { if (starting == - 1 ) { ans[starting + 1 ] = i; // Recursive call find(L, R, starting + 1 , arr, ans); } else { // Check the previous if (i - ans[starting] == arr[starting]) { ans[starting + 1 ] = i; // Recursive call find(L, R, starting + 1 , arr, ans); } } } } // Driver code public static void main(String[] args) { int arr[] = { 1 , - 3 , 4 }; int L = 1 ; int R = 6 ; int ans[] = new int [arr.length + 1 ]; find(L, R, - 1 , arr, ans); if (!flag) System.out.println(- 1 ); } } |
Python3
# Python 3 program to implement the approach # Global variable to note # if any sequence found or not flag = False # Function to find a sequence def find(L, R, starting, arr, ans): if (starting = = len (ans) - 1 ): global flag flag = True for elements in ans: print (elements, end = " " ) print () return # Loop to form the sequence for i in range (L, R + 1 ): if (starting = = - 1 ): ans[starting + 1 ] = i # Recursive call find(L, R, starting + 1 , arr, ans) else : # Check the previous if (i - ans[starting] = = arr[starting]): ans[starting + 1 ] = i # Recursive call find(L, R, starting + 1 , arr, ans) # Driver code if __name__ = = "__main__" : arr = [ 1 , - 3 , 4 ] L = 1 R = 6 ans = [ 0 ] * ( len (arr) + 1 ) find(L, R, - 1 , arr, ans) if ( not flag): print ( - 1 ) # This code is contributed by ukasp. |
C#
// C# program to implement the approach using System; class GFG { // Global variable to note // if any sequence found or not static bool flag = false ; // Function to find a sequence static void find( int L, int R, int starting, int [] arr, int [] ans) { if (starting == ans.Length - 1) { flag = true ; foreach ( int elements in ans) { Console.Write(elements + " " ); } Console.WriteLine(); return ; } // Loop to form the sequence for ( int i = L; i <= R; ++i) { if (starting == -1) { ans[starting + 1] = i; // Recursive call find(L, R, starting + 1, arr, ans); } else { // Check the previous if (i - ans[starting] == arr[starting]) { ans[starting + 1] = i; // Recursive call find(L, R, starting + 1, arr, ans); } } } } // Driver code public static void Main() { int [] arr = { 1, -3, 4 }; int L = 1; int R = 6; int [] ans = new int [arr.Length + 1]; find(L, R, -1, arr, ans); if (!flag) Console.Write(-1); } } // This code is contributed by saurabh_jaiswal. |
Javascript
<script> // JavaScript code for the above approach // Global variable to note // if any sequence found or not let flag = false ; // Function to find a sequence function find(L, R, starting, arr, ans) { if (starting == ans.length - 1) { flag = true ; for (let elements of ans) { document.write(elements + " " ); } document.write( '<br>' ) return ; } // Loop to form the sequence for (let i = L; i <= R; ++i) { if (starting == -1) { ans[starting + 1] = i; // Recursive call find(L, R, starting + 1, arr, ans); } else { // Check the previous if (i - ans[starting] == arr[starting]) { ans[starting + 1] = i; // Recursive call find(L, R, starting + 1, arr, ans); } } } } // Driver code let arr = [1, -3, 4]; let L = 1; let R = 6; let ans = new Array(arr.length + 1).fill(0) find(L, R, -1, arr, ans); if (!flag) document.write(-1); // This code is contributed by Potta Lokesh </script> |
3 4 1 5 4 5 2 6
Time Complexity: O((L-R)*N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!