Horje
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:

  1. 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);
         
    }
}

Output

1 4 3 2 1

Time Complexity: O(N)
Auxiliary Space: O(1)

Related Articles:


 


Reffered: https://www.geeksforgeeks.org

DSA

Related
Minimize division by 2 to make an Array strictly increasing Minimize division by 2 to make an Array strictly increasing
Maximize coins that can be collected by moving on given coordinates Maximize coins that can be collected by moving on given coordinates
Make Array sum even using minimum operations Make Array sum even using minimum operations
Maximum length of sequence formed from cost N Maximum length of sequence formed from cost N
Greedy Best first search algorithm Greedy Best first search algorithm

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 11



 

Horje