Dada una array arr[] de longitud N , con valores menores que N , la tarea es construir otra array A[] de la misma longitud tal que para cada i -ésimo elemento en la array A[] , arr[i] sea el último índice ( indexación basada en 1 ) que consta de un múltiplo de A[i] .
Ejemplos:
Entrada: arr[] = {4, 1, 2, 3, 4}
Salida: 2 3 5 7 2
Explicación:
A[0]: El último índice que puede contener un múltiplo de A[0] tiene que ser A[arr[ 0]] = A[4].
A[1]: El último índice que puede contener un múltiplo de A[1] tiene que ser A[arr[1]] = A[1].
A[2]: El último índice que puede contener un múltiplo de A[2] tiene que ser A[arr[2]] = A[2].
A[3]: El último índice que puede contener un múltiplo de A[3] tiene que ser A[arr[3]] = A[3].
A[4]: El último índice que puede contener un múltiplo de A[4] tiene que ser A[arr[4]] = A[4].
Por lo tanto, en el arreglo final, A[4] debe ser divisible por A[0] y A[1], A[2] y A[3] no deben ser divisibles por ningún otro elemento del arreglo.
Por tanto, el arreglo A[] = {2, 3, 5, 7, 2} satisface la condición.Entrada: arr[] = {0, 1, 2, 3, 4}
Salida: 2 3 5 7 11
Enfoque: la idea es colocar números primos como elementos de array en los índices requeridos que satisfagan las condiciones. Siga los pasos a continuación para resolver el problema:
- Genere todos los números primos usando Sieve Of Eratosthenes y guárdelos en otra array.
- Inicialice la array A[] con {0} para almacenar la array requerida.
- Recorra la array arr[] y realice los siguientes pasos:
- Compruebe si A[arr[i]] no es cero pero A[i] es 0. Si se determina que es cierto, entonces asigne A[i] = A[arr[i]].
- Compruebe si A[arr[i]] y A[i] son 0 o no. Si se determina que es cierto, entonces asigne un número primo diferente a los elementos de array ya asignados, a ambos índices arr[i] e i .
- Después de completar los pasos anteriores, imprima los elementos de la array A[] .
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
2 3 5 7 2
Complejidad de tiempo: O(N*log(log(N)))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA