Given an integer N and an arr1[], of (N – 1) integers, the task is to find the sequence arr2[] of N integers in the range [1, N] such that arr1[i] = arr2[i+1] – arr2[i]. The integers in sequence arr1[] lies in range [-N, N].
Examples:
Input: N = 3, arr1[] = {-2, 1}
Output: arr2[] = {3, 1, 2}
Explanation:
arr2[1] – arr2[0] = (1 – 3) = -2 = arr1[0]
arr2[2] – arr2[1] = (2 – 1) = 1 = arr1[1]
Input: N = 5, arr1 = {1, 1, 1, 1, 1}
Output: arr2 = {1, 2, 3, 4, 5}
Explanation:
arr2[1] – arr2[0] = (2 – 1) = 1 = arr1[0]
arr2[2] – arr2[1] = (3 – 2) = 1 = arr1[1]
arr2[3] – arr2[2] = (4 – 3) = 1 = arr1[2]
arr2[4] – arr2[3] = (5 – 4) = 1 = arr1[3]
Approach:
Follow the steps to solve the problem:
- Assume the first element of arr2[] to be X.
- The next element will be X + arr1[0].
- The rest of the elements of arr2[] can be represented, w.r.t X.
- It is known that the sequence arr2[] can contain integers in the range [1, N]. So the minimum possible integer would be 1.
- The minimum number of the arr2[] can be found out in terms of X, and equate it with 1 to find the value of X.
- Finally using the values of X, all the other numbers in arr2[] can be found out.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the sequencevoid find_seq(int arr[], int m, int n) { int b[n]; int x = 0; // initializing 1st element b[0] = x; // Creating sequence in // terms of x for (int i = 0; i < n - 1; i++) { b[i + 1] = x + arr[i] + b[i]; } int mn = n; // Finding min element for (int i = 0; i < n; i++) { mn = min(mn, b[i]); } // Finding value of x x = 1 - mn; // Creating original sequence for (int i = 0; i < n; i++) { b[i] += x; } // Output original sequence for (int i = 0; i < n; i++) { cout << b[i] << " "; } cout << endl;}// Driver functionint main(){ int N = 3; int arr[] = { -2, 1 }; int M = sizeof(arr) / sizeof(int); find_seq(arr, M, N); return 0;} |
Java
// Java implementation of the above approach class GFG{ // Function to find the sequencestatic void find_seq(int arr[], int m, int n){ int b[] = new int[n]; int x = 0; // Initializing 1st element b[0] = x; // Creating sequence in // terms of x for(int i = 0; i < n - 1; i++) { b[i + 1] = x + arr[i] + b[i]; } int mn = n; // Finding min element for(int i = 0; i < n; i++) { mn = Math.min(mn, b[i]); } // Finding value of x x = 1 - mn; // Creating original sequence for(int i = 0; i < n; i++) { b[i] += x; } // Output original sequence for(int i = 0; i < n; i++) { System.out.print(b[i] + " "); } System.out.println();} // Driver code public static void main (String[] args) { int N = 3; int arr[] = new int[]{ -2, 1 }; int M = arr.length; find_seq(arr, M, N);} } // This code is contributed by Pratima Pandey |
Python3
# Python3 program for the above approach# Function to find the sequencedef find_seq(arr, m, n): b = [] x = 0 # Initializing 1st element b.append(x) # Creating sequence in # terms of x for i in range(n - 1): b.append(x + arr[i] + b[i]) mn = n # Finding min element for i in range(n): mn = min(mn, b[i]) # Finding value of x x = 1 - mn # Creating original sequence for i in range(n): b[i] += x # Output original sequence for i in range(n): print(b[i], end = ' ') print() # Driver codeif __name__=='__main__': N = 3 arr = [ -2, 1 ] M = len(arr) find_seq(arr, M, N)# This code is contributed by rutvik_56 |
C#
// C# implementation of the above approach using System;class GFG{ // Function to find the sequencestatic void find_seq(int []arr, int m, int n){ int []b = new int[n]; int x = 0; // Initializing 1st element b[0] = x; // Creating sequence in // terms of x for(int i = 0; i < n - 1; i++) { b[i + 1] = x + arr[i] + b[i]; } int mn = n; // Finding min element for(int i = 0; i < n; i++) { mn = Math.Min(mn, b[i]); } // Finding value of x x = 1 - mn; // Creating original sequence for(int i = 0; i < n; i++) { b[i] += x; } // Output original sequence for(int i = 0; i < n; i++) { Console.Write(b[i] + " "); } Console.WriteLine();} // Driver code public static void Main(String[] args) { int N = 3; int []arr = new int[]{ -2, 1 }; int M = arr.Length; find_seq(arr, M, N);} }// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program for the above approach// Function to find the sequencefunction find_seq(arr,m, n) { let b = new Array(n); let x = 0; // initializing 1st element b[0] = x; // Creating sequence in // terms of x for (let i = 0; i < n - 1; i++) { b[i + 1] = x + arr[i] + b[i]; } let mn = n; // Finding min element for (let i = 0; i < n; i++) { mn = Math.min(mn, b[i]); } // Finding value of x x = 1 - mn; // Creating original sequence for (let i = 0; i < n; i++) { b[i] += x; } // Output original sequence for (let i = 0; i < n; i++) { document.write(b[i] + " "); } document.write("<br>");}// Driver function let N = 3; let arr = [ -2, 1 ]; let M = arr.length; find_seq(arr, M, N); // This code is contributed by Mayank Tyagi</script> |
Output:
3 1 2
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
