Construya una array de longitud N que contenga exactamente K elementos divisibles por sus posiciones

Dados dos enteros N y K, la tarea es construir una array de longitud N que contenga exactamente K elementos divisibles por sus posiciones.

Ejemplos:

Entrada : N = 6, K = 2
Salida: {5, 1, 2, 3, 4, 6}
Explicación: Considerando la array anterior:
En la Posición 1, el elemento 5 es divisible por 1
En la Posición 2, el elemento 1 no es divisible por 2
En la posición 3, el elemento 2 no es divisible por 3
En la posición 4, el elemento 3 no es divisible por 4
En la posición 5, el elemento 4 no es divisible por 5
En la posición 6, el elemento 6 es divisible por 6
Por lo tanto, hay exactamente K elementos en array divisible por sus posiciones, cumpliendo los criterios requeridos.
Por lo tanto, la array resultante será {5 1 2 3 4 6}.

Entrada: N = 5, K = 5
Salida: {1, 2, 3, 4, 5}

Enfoque: el problema se puede resolver fácilmente utilizando el enfoque Greedy basado en las siguientes observaciones:

Para cualquier entero X, sabemos que:

• X será divisible por 1 y X siempre.
• Ningún entero mayor que X podrá nunca dividir X.

Entonces, usando estas observaciones, podemos construir la array que contiene exactamente K elementos divisibles por sus posiciones, de la siguiente manera:

• Para la posición 1, coloque cualquier elemento mayor que 1, porque 1 dividirá todos los números enteros
• Para posiciones mayores que 1, elija posiciones K-1 y colóquelas en la array en los índices correspondientes.
• Las posiciones NK restantes se pueden colocar en cualquier otra posición para cumplir con los criterios requeridos.

Ilustraciones:

Considere un ejemplo: N = 6, K = 5

La array vacía de tamaño 6 será: 
arr[]: _ _ _ _ _ _
posiciones: 1 2 3 4 5 6

Paso 1: Rellene la posición 1 con cualquier número entero mayor que 1

• Para el primer valor igual a su posición, tenemos 2 opciones: insertar 1 en 1 e insertar algún número entero mayor que 1 en 1. Si insertamos 1 en 1, habrá un caso en el que no podamos tener valores K = 5 igual que sus posiciones. Así que insertaremos algún otro valor mayor que 1 en la posición 1 (digamos 5):
  • arr[]: 5 _ _ _ _ _
    posiciones: 1 2 3 4 5 6

Paso 2: Rellene las posiciones K-1 (=4) en los índices correspondientes

• Para 2º valor igual a su posición:
  • arr[]: 5 2 _ _ _ _
    posiciones: 1 2 3 4 5 6
• Para el 3er valor igual a su posición:
  • arr[]: 5 2 3 _ _ _
    posiciones: 1 2 3 4 5 6
• Para el 4º valor igual a su posición:
  • arr[]: 5 2 3 4 _ _
    posiciones: 1 2 3 4 5 6
• Para el quinto valor igual a su posición, no podemos insertar 5 en la posición 5, ya que ya se usa en la posición 1. Entonces, insertaremos 1 en la posición 5 y 6 en la posición 6:
  • arr[]: 5 2 3 4 1 6
    posiciones: 1 2 3 4 5 6

Por lo tanto la array final será: 5 2 3 4 1 6

Siga los pasos a continuación para implementar el enfoque anterior:

• Cree una array de N enteros positivos consecutivos de 1 a N .
• Después del índice NK , quedarán elementos K-1 , no interferiremos con estos elementos. Entonces, tenemos elementos K-1 , que son divisibles por su posición.
• Haremos que el primer elemento de la array sea igual al elemento en el índice NK . Esto también sería divisible por su posición.
• Haremos que los elementos restantes (es decir, desde el índice 1 hasta NK ) sean iguales a los elementos que les quedan inmediatamente. Todos estos elementos NK no serán divisibles por su posición entonces y los elementos K restantes serían divisibles por su posición.

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

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to construct an array of size
// N such that it contains all numbers from
// 1 to N and only K elements are divisible by
// their position (i.e. index+1)
vector<int> constructArray(int N, int K)
{
    // Declaring array of size N
    vector<int> A(N, 0);
 
    // Initializing array as {1, 2, 3....N}
    for (int i = 0; i < N; i++) {
        A[i] = i + 1;
    }
 
    // N-K index stored in a variable "target"
    // After target there will be k-1 elements
    // which are divisible by their position
    int target = N - K;
 
    // Initializing "prev" variable that helps in
    // shifting elements to their right
    int prev = A[0];
 
    // Assigning first element the value at target
    // index
    A[0] = A[target];
 
    // Making all elements from index 1 to target
    // equal to their immediate left element
    // as any number would not be divisible
    // by its next number
    for (int i = 1; i <= target; i++) {
        int temp = A[i];
        A[i] = prev;
        prev = temp;
    }
 
    return A;
}
 
// Driver Code
int main()
{
    int N = 6, K = 2;
 
    // Calling function
    // to construct the array
    vector<int> A = constructArray(N, K);
 
    // Printing resultant array
    for (int i = 0; i < N; i++)
        cout << A[i] << " ";
    cout << endl;
}

// JAVA program for above approach
import java.util.*;
class GFG
{
   
    // Function to construct an array of size
    // N such that it contains all numbers from
    // 1 to N and only K elements are divisible by
    // their position (i.e. index+1)
    public static int[] constructArray(int N, int K)
    {
       
        // Declaring array of size N
        int A[] = new int[N];
        for (int i = 0; i < A.length; ++i) {
            A[i] = 0;
        }
 
        // Initializing array as {1, 2, 3....N}
        for (int i = 0; i < N; i++) {
            A[i] = i + 1;
        }
 
        // N-K index stored in a variable "target"
        // After target there will be k-1 elements
        // which are divisible by their position
        int target = N - K;
 
        // Initializing "prev" variable that helps in
        // shifting elements to their right
        int prev = A[0];
 
        // Assigning first element the value at target
        // index
        A[0] = A[target];
 
        // Making all elements from index 1 to target
        // equal to their immediate left element
        // as any number would not be divisible
        // by its next number
        for (int i = 1; i <= target; i++) {
            int temp = A[i];
            A[i] = prev;
            prev = temp;
        }
 
        return A;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 6, K = 2;
 
        // Calling function
        // to construct the array
        int A[] = constructArray(N, K);
 
        // Printing resultant array
        for (int i = 0; i < N; i++)
            System.out.print(A[i] + " ");
        System.out.println();
    }
}
 
// This code is contributed by Taranpreet

# Python program for above approach
 
# Function to construct an array of size
# N such that it contains all numbers from
# 1 to N and only K elements are divisible by
# their position (i.e. index+1)
def constructArray(N, K):
   
    # Declaring array of size N
    A = [0]*N
 
    # Initializing array as {1, 2, 3....N}
    for i in range(N):
      A[i] = i + 1
 
    # N-K index stored in a variable "target"
    # After target there will be k-1 elements
    # which are divisible by their position
    target = N - K
 
    # Initializing "prev" variable that helps in
    # shifting elements to their right
    prev = A[0]
 
    # Assigning first element the value at target
    # index
    A[0] = A[target]
 
    # Making all elements from index 1 to target
    # equal to their immediate left element
    # as any number would not be divisible
    # by its next number
    for i in range(1,target+1):
        temp = A[i]
        A[i] = prev
        prev = temp
 
    return A
 
# Driver Code
N = 6
K = 2
 
# Calling function
# to construct the array
A = constructArray(N, K)
 
# Printing resultant array
for i in range(N):
   print(A[i],end=" ")
 
# This code is contributed by shinjanpatra

// C# program for above approach
using System;
class GFG {
 
  // Function to construct an array of size
  // N such that it contains all numbers from
  // 1 to N and only K elements are divisible by
  // their position (i.e. index+1)
  static int[] constructArray(int N, int K)
  {
 
    // Declaring array of size N
    int[] A = new int[N];
    for (int i = 0; i < A.Length; ++i) {
      A[i] = 0;
    }
 
    // Initializing array as {1, 2, 3....N}
    for (int i = 0; i < N; i++) {
      A[i] = i + 1;
    }
 
    // N-K index stored in a variable "target"
    // After target there will be k-1 elements
    // which are divisible by their position
    int target = N - K;
 
    // Initializing "prev" variable that helps in
    // shifting elements to their right
    int prev = A[0];
 
    // Assigning first element the value at target
    // index
    A[0] = A[target];
 
    // Making all elements from index 1 to target
    // equal to their immediate left element
    // as any number would not be divisible
    // by its next number
    for (int i = 1; i <= target; i++) {
      int temp = A[i];
      A[i] = prev;
      prev = temp;
    }
 
    return A;
  }
 
  // Driver Code
  public static void Main()
  {
    int N = 6, K = 2;
 
    // Calling function
    // to construct the array
    int[] A = constructArray(N, K);
 
    // Printing resultant array
    for (int i = 0; i < N; i++)
      Console.Write(A[i] + " ");
    Console.WriteLine();
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
    // JavaScript program for above approach
 
    // Function to construct an array of size
    // N such that it contains all numbers from
    // 1 to N and only K elements are divisible by
    // their position (i.e. index+1)
    const constructArray = (N, K) => {
        // Declaring array of size N
        let A = new Array(N).fill(0);
 
        // Initializing array as {1, 2, 3....N}
        for (let i = 0; i < N; i++) {
            A[i] = i + 1;
        }
 
        // N-K index stored in a variable "target"
        // After target there will be k-1 elements
        // which are divisible by their position
        let target = N - K;
 
        // Initializing "prev" variable that helps in
        // shifting elements to their right
        let prev = A[0];
 
        // Assigning first element the value at target
        // index
        A[0] = A[target];
 
        // Making all elements from index 1 to target
        // equal to their immediate left element
        // as any number would not be divisible
        // by its next number
        for (let i = 1; i <= target; i++) {
            let temp = A[i];
            A[i] = prev;
            prev = temp;
        }
 
        return A;
    }
 
    // Driver Code
 
    let N = 6, K = 2;
 
    // Calling function
    // to construct the array
    let A = constructArray(N, K);
 
    // Printing resultant array
    for (let i = 0; i < N; i++)
        document.write(`${A[i]} `);
 
// This code is contributed by rakeshsahni
 
</script>

5 1 2 3 4 6 

Complejidad temporal:   O(N)
Espacio auxiliar:   O(N)