Genere una array tal que max se minimice y arr[i] != arr[j] cuando j es un múltiplo de i

Dado un entero N , la tarea es generar un arreglo arr[] que tenga N enteros positivos tales que arr[i] ≠ arr[j] si j es divisible por i (se considera la indexación basada en 1) tal que el valor máximo de la secuencia es mínima entre todas las secuencias posibles.

Ejemplos:

Entrada: N = 3
Salida: 1 2 2
Explicación: En esta secuencia 2 es divisible por 1. arr[2] = 2, arr[1] = 1 y arr[2] ≠ arr[1].
En esta sucesión 3 es divisible por 1. arr[3] = 2, arr[1] = 1 y arr[3] ≠ arr[1].
El valor máximo es 2, que es el mínimo posible entre todas las secuencias.

Entrada: N = 1
Salida: 1

Planteamiento: Este problema se puede resolver a partir de la siguiente idea:

Para cada índice i , el valor de arr[i] debe ser al menos igual al número de divisores que tiene (incluido el número en sí). 
En lugar de encontrar directamente divisores para cada número, también se pueden encontrar múltiplos (digamos j ) de cada índice i . e incrementar el conteo de divisores de j .

Siga la ilustración dada a continuación para una mejor comprensión.

Diga N = 3.
Cree arr[] = {0, 0, 0} para almacenar el número de divisores de cada valor.

Para i = 1:
            => Los múltiplos de 1 son 1, 2 y 3.
            => Incrementar los valores de arr[1], arr[2] y arr[3].
            => Entonces arr[] = {1, 1, 1}

Para i = 1:
            => Múltiplos de 2 es 2.
            => Valor de incremento de arr[2].
            => Entonces arr[] = {1, 2, 1}

Para i = 3:
            => Múltiplos de 3 es 3.
            => Valor incremental de arr[3].
            => Entonces arr[] = {1, 2, 2}

Entonces, la array final es arr = {1, 2, 2} donde el valor máximo (es decir, 2) es el mínimo entre todas las secuencias posibles.

Siga los pasos mencionados a continuación para implementar la observación anterior:

• Cree una array de tamaño N (digamos arr[] ) con todos los elementos inicialmente llenos con 0.
• Usa la criba de Eratóstenes para encontrar todos los múltiplos de todos los números desde i = 1 hasta N .
• Para este recorrido de i = 1 a N :
  • Ejecute un ciclo de j = i a N e incremente j por i en cada paso:
    • Incremente el valor de arr[j] en 1.
• Devuelve la array final.

A continuación se muestra la implementación del enfoque anterior.

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to generate the array
vector<int> goodSequence(int N)
{
    vector<int> res(N);
    res[0] = 1;
 
    // Loop to implement
    // sieve of Eratosthenes
    for (int i = 1; i * i <= N; i++) {
        for (int j = 2 * i; j <= N; j += i)
            res[j - 1] = res[i - 1] + 1;
    }
    return res;
}
 
// Driver code
int main()
{
    int N = 3;
 
    // Function call
    vector<int> ans = goodSequence(N);
    for (int x : ans)
        cout << x << " ";
    return 0;
}

// Java code to implement the approach
import java.io.*;
 
class GFG {
 
  // Function to generate the array
  static int[] goodSequence(int N)
  {
    int[] res = new int[N];
    res[0] = 1;
 
    // Loop to implement
    // sieve of Eratosthenes
    for (int i = 1; i * i <= N; i++) {
      for (int j = 2 * i; j <= N; j += i)
        res[j - 1] = res[i - 1] + 1;
    }
    return res;
  }
 
  // Driver code
  public static void main (String[] args) {
    int N = 3;
 
    // Function call
    int ans[] = goodSequence(N);
    for (int x = 0; x < ans.length; x++)
      System.out.print(ans[x] + " ");
  }
 
}
 
// This code is contributed by hrithikgarg03188.

# python3 code to implement the approach
 
import math
 
# Function to generate the array
 
 
def goodSequence(N):
 
    res = [0 for _ in range(N)]
    res[0] = 1
 
    # Loop to implement
    # sieve of Eratosthenes
    for i in range(1, int(math.sqrt(N)) + 1):
        for j in range(2*i, N+1, i):
            res[j - 1] = res[i - 1] + 1
 
    return res
 
 
# Driver code
if __name__ == "__main__":
 
    N = 3
 
    # Function call
    ans = goodSequence(N)
    for x in ans:
        print(x, end=" ")
 
    # This code is contributed by rakeshsahni

// C# code to implement the approach
using System;
class GFG {
 
    // Function to generate the array
    static int[] goodSequence(int N)
    {
        int[] res = new int[N];
        res[0] = 1;
 
        // Loop to implement
        // sieve of Eratosthenes
        for (int i = 1; i * i <= N; i++) {
            for (int j = 2 * i; j <= N; j += i)
                res[j - 1] = res[i - 1] + 1;
        }
        return res;
    }
 
    // Driver code
    public static void Main()
    {
        int N = 3;
 
        // Function call
        int[] ans = goodSequence(N);
        for (int x = 0; x < ans.Length; x++)
            Console.Write(ans[x] + " ");
    }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
       // JavaScript code for the above approach
 
       // Function to generate the array
       function goodSequence(N) {
           let res = new Array(N);
           res[0] = 1;
 
           // Loop to implement
           // sieve of Eratosthenes
           for (let i = 1; i * i <= N; i++) {
               for (let j = 2 * i; j <= N; j += i)
                   res[j - 1] = res[i - 1] + 1;
           }
           return res;
       }
 
       // Driver code
       let N = 3;
 
       // Function call
       let ans = goodSequence(N);
       for (let x of ans)
           document.write(x + " ")
 
       // This code is contributed by Potta Lokesh
   </script>

1 2 2 

Complejidad de tiempo: O(N*log(log(N)))
Espacio auxiliar: O(N)