Create Y[] by given Array X[] following given condition
Given an array X[] of length N, Where (1 ? Xi ? N). Create an array Y[], where the element at Y[i] should divide an element present at Y[X[i]-1]. and (X[i]-1) is the maximum such position in which the element is divisible by Y[i].
Note: If there are multiple possible arrays Y[]. Then print any one of them.
Examples:
Input: N = 5, X[] = {5, 2, 3, 4, 5}
Output: Y[] = {2, 6, 5, 3, 4}
Explanation: At index 1: Y1 = 2 divides 2, 6, and 4 at indices 0, 1, and 4 respectively. Max index = 4.
At index 2: Y2 = 6 divides only itself at index 2. Max index = 1.
At index 3: Y3 = 5 divides only itself at index 3. Max index = 2.
At index 4: Y4 = 3 divides only itself only index 4. Max index = 3.
At index 5: Y5 = 4 divides only itself only index 5. Max index = 4.
So the array of max indices becomes X[] = {5, 2, 3, 4, 5}. Output array Y[] satisfies the given constraints of the problem.Input: N= 3, X[] = {3, 3, 3}
Output: Y[] = {1, 1, 1}
Explanation: It can be verified that output array Y[] satisfies the given constraints of the problem.
Approach: The problem can be solved based on the following idea:
The problem is observation based and can be solved via iterating over X[] and output N + 1 – X[i] over each iteration. It should be noted that X[] contains maximum values of index such that Yi divides Y[X[i]-1]. Therefore, greater indices will contain smaller elements and small indices will contain large elements. This gives us approach that, We should traverse over X[] and output N+1-X[i] at each iteration.
Steps were taken to solve the problem:
- Run a loop from i = 0 to less than N and follow the steps at each iteration:
- Print N + 1 – X[i] for each index.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <iostream> using namespace std; // Function to create array Y[] from X[] void createY( int X[], int N) { for ( int i = 0; i < N; i++) { cout<< (N + 1 - X[i]) << " " ; } } int main() { int N = 5; int X[] = { 5, 2, 3, 4, 5 }; // Function call createY(X, N); return 0; } // This code is contributed by rahulbhardwaj0711 |
Java
// Java code to implement the approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Driver code public static void main(String[] args) throws java.lang.Exception { int N = 5 ; int X[] = { 5 , 2 , 3 , 4 , 5 }; // Function call createY(X, N); } // Function to create array Y[] from // X[] public static void createY( int X[], int N) { for ( int i = 0 ; i < N; i++) { System.out.print((N + 1 - X[i]) + " " ); } } } |
Python3
# Python code for the above approach #Function to create array Y[] from X[] def createY(X, N): for i in range (N): print ((N + 1 - X[i])) # Driver code N = 5 X = [ 5 , 2 , 3 , 4 , 5 ] # Function call createY(X, N) #This code is contributed by Potta Lokesh |
Javascript
// JavaScript code to implement the approach // Function to create array Y[] from X[] function createY(X, N) { for (let i = 0; i < N; i++) { console.log((N + 1 - X[i])); } } \\ Driver code let N = 5; let X = [5, 2, 3, 4, 5 ]; // Function call createY(X, N); // This code is contributed by poojaagarwal2. |
C#
// C# code to implement the approach using System; using System.Collections.Generic; // Function to create array Y[] from X[] public class Gfg { static void createY( int [] X, int N) { for ( int i = 0; i < N; i++) { Console.WriteLine((N + 1 - X[i])); } } public static void Main(String[] args) { int N = 5; int [] X = { 5, 2, 3, 4, 5 }; // Function call createY(X, N); } } |
1 4 3 2 1
Time Complexity: O(N)
Auxiliary Space: O(1)
Related Articles: