Given an array arr[] of length N, with values less than N, the task is to construct another array A[] of same length such that for every ith element in the array A[], arr[i] is the last index (1-based indexing) consisting of a multiple of A[i].
Examples:
Input: arr[] = {4, 1, 2, 3, 4}
Output: 2 3 5 7 2
Explanation:
A[0]: Last index which can contain a multiple of A[0] has to be A[arr[0]] = A[4].
A[1]: Last index which can contain a multiple of A[1] has to be A[arr[1]] = A[1].
A[2]: Last index which can contain a multiple of A[2] has to be A[arr[2]] = A[2].
A[3]: Last index which can contain a multiple of A[3] has to be A[arr[3]] = A[3].
A[4]: Last index which can contain a multiple of A[4] has to be A[arr[4]] = A[4].
Hence, in the final array, A[4] must be divisible by A[0] and A[1], A[2] and A[3] must not be divisible by any other array elements.
Hence, the array A[] = {2, 3, 5, 7, 2} satisfies the condition.Input: arr[] = {0, 1, 2, 3, 4}
Output: 2 3 5 7 11
Approach: The idea is to place prime numbers as array elements in required indices satisfying the conditions. Follow the steps below to solve the problem:
- Generate all Prime Numbers using Sieve Of Eratosthenes and store it in another array.
- Initialize array A[] with {0}, to store the required array.
- Traverse the array arr[] and perform the following steps:
- Check if A[arr[i]] is non-zero but A[i] is 0. If found to be true, then assign A[i] = A[arr[i]].
- Check if A[arr[i]] and A[i] are both 0 or not. If found to be true, then assign a prime number different to already assigned array elements, to both indices arr[i] and i.
- After completing the above steps, print the elements of array A[].
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; int sieve[1000000]; // Function to generate all // prime numbers upto 10^6 void sieveOfPrimes() { // Initialize sieve[] as 1 memset (sieve, 1, sizeof (sieve)); int N = 1000000; // Iterate over the range [2, N] for ( int i = 2; i * i <= N; i++) { // If current element is non-prime if (sieve[i] == 0) continue ; // Make all multiples of i as 0 for ( int j = i * i; j <= N; j += i) sieve[j] = 0; } } // Function to construct an array A[] // satisfying the given conditions void getArray( int * arr, int N) { // Stores the resultant array int A[N] = { 0 }; // Stores all prime numbers vector< int > v; // Sieve of Eratosthenes sieveOfPrimes(); for ( int i = 2; i <= 1e5; i++) // Append the integer i // if it is a prime if (sieve[i]) v.push_back(i); // Indicates current position // in list of prime numbers int j = 0; // Traverse the array arr[] for ( int i = 0; i < N; i++) { int ind = arr[i]; // If already filled with // another prime number if (A[i] != 0) continue ; // If A[i] is not filled // but A[ind] is filled else if (A[ind] != 0) // Store A[i] = A[ind] A[i] = A[ind]; // If none of them were filled else { // To make sure A[i] does // not affect other values, // store next prime number int prime = v[j++]; A[i] = prime; A[ind] = A[i]; } } // Print the resultant array for ( int i = 0; i < N; i++) { cout << A[i] << " " ; } } // Driver Code int main() { int arr[] = { 4, 1, 2, 3, 4 }; int N = sizeof (arr) / sizeof (arr[0]); // Function Call getArray(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { static int [] sieve = new int [ 10000000 ]; // Function to generate all // prime numbers upto 10^6 static void sieveOfPrimes() { // Initialize sieve[] as 1 Arrays.fill(sieve, 1 ); int N = 1000000 ; // Iterate over the range [2, N] for ( int i = 2 ; i * i <= N; i++) { // If current element is non-prime if (sieve[i] == 0 ) continue ; // Make all multiples of i as 0 for ( int j = i * i; j <= N; j += i) sieve[j] = 0 ; } } // Function to construct an array A[] // satisfying the given conditions static void getArray( int [] arr, int N) { // Stores the resultant array int A[] = new int [N]; Arrays.fill(A, 0 ); // Stores all prime numbers ArrayList<Integer> v = new ArrayList<Integer>(); // Sieve of Eratosthenes sieveOfPrimes(); for ( int i = 2 ; i <= 1000000 ; i++) // Append the integer i // if it is a prime if (sieve[i] != 0 ) v.add(i); // Indicates current position // in list of prime numbers int j = 0 ; // Traverse the array arr[] for ( int i = 0 ; i < N; i++) { int ind = arr[i]; // If already filled with // another prime number if (A[i] != 0 ) continue ; // If A[i] is not filled // but A[ind] is filled else if (A[ind] != 0 ) // Store A[i] = A[ind] A[i] = A[ind]; // If none of them were filled else { // To make sure A[i] does // not affect other values, // store next prime number int prime = v.get(j++); A[i] = prime; A[ind] = A[i]; } } // Print the resultant array for ( int i = 0 ; i < N; i++) { System.out.print( A[i] + " " ); } } // Driver Code public static void main(String[] args) { int arr[] = { 4 , 1 , 2 , 3 , 4 }; int N = arr.length; // Function Call getArray(arr, N); } } // This code is contributed by code_hunt. |
Python3
# Python3 program for the above approach sieve = [ 1 ] * ( 1000000 + 1 ) # Function to generate all # prime numbers upto 10^6 def sieveOfPrimes(): global sieve N = 1000000 # Iterate over the range [2, N] for i in range ( 2 , N + 1 ): if i * i > N: break # If current element is non-prime if (sieve[i] = = 0 ): continue # Make all multiples of i as 0 for j in range (i * i, N + 1 , i): sieve[j] = 0 # Function to construct an array A[] # satisfying the given conditions def getArray(arr, N): global sieve # Stores the resultant array A = [ 0 ] * N # Stores all prime numbers v = [] # Sieve of Eratosthenes sieveOfPrimes() for i in range ( 2 , int ( 1e5 ) + 1 ): # Append the integer i # if it is a prime if (sieve[i]): v.append(i) # Indicates current position # in list of prime numbers j = 0 # Traverse the array arr[] for i in range (N): ind = arr[i] # If already filled with # another prime number if (A[i] ! = 0 ): continue # If A[i] is not filled # but A[ind] is filled elif (A[ind] ! = 0 ): # Store A[i] = A[ind] A[i] = A[ind] # If none of them were filled else : # To make sure A[i] does # not affect other values, # store next prime number prime = v[j] A[i] = prime A[ind] = A[i] j + = 1 # Print the resultant array for i in range (N): print (A[i], end = " " ) # Driver Code if __name__ = = '__main__' : arr = [ 4 , 1 , 2 , 3 , 4 ] N = len (arr) # Function Call getArray(arr, N) # This code is contributed by mohit kumar 29. |
C#
// C# Program to implement // the above approach using System; using System.Collections.Generic; class GFG { static int [] sieve = new int [10000000]; // Function to generate all // prime numbers upto 10^6 static void sieveOfPrimes() { // Initialize sieve[] as 1 for ( int i = 0; i < 10000000; i++) { sieve[i] = 1; } int N = 1000000; // Iterate over the range [2, N] for ( int i = 2; i * i <= N; i++) { // If current element is non-prime if (sieve[i] == 0) continue ; // Make all multiples of i as 0 for ( int j = i * i; j <= N; j += i) sieve[j] = 0; } } // Function to construct an array A[] // satisfying the given conditions static void getArray( int [] arr, int N) { // Stores the resultant array int [] A = new int [N]; for ( int i = 0; i < N; i++) { A[i] = 0; } // Stores all prime numbers List< int > v = new List< int >(); // Sieve of Eratosthenes sieveOfPrimes(); for ( int i = 2; i <= 1000000; i++) // Append the integer i // if it is a prime if (sieve[i] != 0) v.Add(i); // Indicates current position // in list of prime numbers int j = 0; // Traverse the array arr[] for ( int i = 0; i < N; i++) { int ind = arr[i]; // If already filled with // another prime number if (A[i] != 0) continue ; // If A[i] is not filled // but A[ind] is filled else if (A[ind] != 0) // Store A[i] = A[ind] A[i] = A[ind]; // If none of them were filled else { // To make sure A[i] does // not affect other values, // store next prime number int prime = v[j++]; A[i] = prime; A[ind] = A[i]; } } // Print the resultant array for ( int i = 0; i < N; i++) { Console.Write( A[i] + " " ); } } // Driver Code public static void Main(String[] args) { int [] arr = { 4, 1, 2, 3, 4 }; int N = arr.Length; // Function Call getArray(arr, N); } } // This code is contributed by splevel62. |
Javascript
<script> // JavaScript program for the above approach var sieve = Array(1000000); // Function to generate all // prime numbers upto 10^6 function sieveOfPrimes() { // Initialize sieve[] as 1 sieve = Array(1000000).fill(1); var N = 1000000; // Iterate over the range [2, N] for ( var i = 2; i * i <= N; i++) { // If current element is non-prime if (sieve[i] == 0) continue ; // Make all multiples of i as 0 for ( var j = i * i; j <= N; j += i) sieve[j] = 0; } } // Function to construct an array A[] // satisfying the given conditions function getArray(arr, N) { // Stores the resultant array var A = Array(N).fill(0); // Stores all prime numbers var v = []; // Sieve of Eratosthenes sieveOfPrimes(); for ( var i = 2; i <= 1e5; i++) // Append the integer i // if it is a prime if (sieve[i]) v.push(i); // Indicates current position // in list of prime numbers var j = 0; // Traverse the array arr[] for ( var i = 0; i < N; i++) { var ind = arr[i]; // If already filled with // another prime number if (A[i] != 0) continue ; // If A[i] is not filled // but A[ind] is filled else if (A[ind] != 0) // Store A[i] = A[ind] A[i] = A[ind]; // If none of them were filled else { // To make sure A[i] does // not affect other values, // store next prime number var prime = v[j++]; A[i] = prime; A[ind] = A[i]; } } // Print the resultant array for ( var i = 0; i < N; i++) { document.write( A[i] + " " ); } } // Driver Code var arr = [4, 1, 2, 3, 4]; var N = arr.length; // Function Call getArray(arr, N); </script> |
2 3 5 7 2
Time Complexity: O(N*log(log(N)))
Auxiliary Space: O(N)