Construir array de tamaño dado con elementos en posiciones pares divisible por su izquierda adyacente

Dado un número entero N , la tarea es construir e imprimir un Array, tal que:

• El tamaño de la array es N
• Los elementos de la array están en el rango [1, 2*N]
• Cada elemento en la array es distinto.
• Los elementos en posiciones pares son divisibles por su lado izquierdo adyacente, pero esto no debe ser cierto para los elementos en posiciones impares, es decir 
  • arr[i] % arr[i-1] == 0 es verdadero para i % 2 == 0
  • arr[i] % arr[i-1] != 0 es verdadero para i % 2 != 0
• Se considera que la array está indexada en 1.

Ejemplos:

Entrada: N = 4 
Salida: {1, 3, 2, 4}
Explicación: 
Para i = 1, A[2] % A[1] = 3 % 1 = 0
Para i = 2 . A[3] % A[2] = 2 % 3 ≠ 0
Para i = 3, A[4] % A[3] = 4 % 2 = 0

Entrada: N = 7
Salida: {1, 2, 3, 6, 5, 10, 7}

Enfoque: puede haber varias arrays de tamaño N según las condiciones dadas. Aquí hay un enfoque codicioso simple para construir uno entre ellos, basado en la siguiente observación:

La secuencia {X, 2*X, X+2, 2*(X+2)….} cumplirá siempre todas las condiciones del problema para X = 1, 3, 4, … y así sucesivamente , como:

De acuerdo con la secuencia anterior,  
    primer par de elementos = X y 2(X)
    segundo par de elementos = X+2 y 2(X+2)
    tercer par de elementos = X+4 y 2(X+4)
    .
    .
    Par de elementos Cth = X+2C y 2(X+2C)

Por lo tanto, para cualquier par de elementos Cth,

• Cada elemento de Array siempre será distinto.
• El elemento en la posición par 2 (X+2C) siempre será divisible por su lado izquierdo adyacente (X+2C)
• El elemento en posición impar (X+2C) nunca será divisible por su 2 izquierdo adyacente (X+2C-2)

Por lo tanto, esta secuencia siempre será válida para el Array requerido.

Nota: No podemos considerar {X, 2*X, X+1, 2*(X+1)….} ya que los elementos pueden duplicarse para este caso cuando X = 1. Otra secuencia válida será {X, 2 *X, X+1, 2*(X+1)….} para X > 1.

Con base en la observación anterior, se puede utilizar el siguiente enfoque para resolver el problema:

Para este enfoque, simplemente podemos considerar la array construida con X = 1 según la secuencia anterior, como una de las posibles soluciones.

• Declare una array de tamaño N+1 para almacenar la respuesta e inicialice una variable X por 1.
• Iterar de 1 a N.
• En cada índice impar, almacene enteros impares consecutivos.
• En cada índice par, almacene el doble del entero en el índice anterior.

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

// C++ Code for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find an array such
// that elements at even positions
// are divisible by their previous
// element and elements at odd positions
// are not
void constructArray(int N)
{
    // Declaring array A to store the answer
    int ans[N + 1];
 
    // Initializing a variable X by 1
    int X = 1;
 
    // Iterating from 1 to N and storing
    // consecutive odd integers at odd
    // indices and twice of element at
    // previous index at even indices
    for (int i = 1; i <= N; i++) {
        if (i % 2 == 1) {
            ans[i] = X;
        }
        else {
            ans[i] = 2 * ans[i - 1];
            X += 2;
        }
    }
 
    // Printing the array
    for (int i = 1; i <= N; i++) {
        cout << ans[i] << " ";
    }
}
 
// Driver Code
int main()
{
    int N = 7;
    constructArray(N);
 
    return 0;
}

// Java Code for above approach
import java.io.*;
 
class GFG {
 
// Function to find an array such
// that elements at even positions
// are divisible by their previous
// element and elements at odd positions
// are not
  static void constructArray(int N)
{
    // Declaring array A to store the answer
    int ans[] = new int[N + 1];
 
    // Initializing a variable X by 1
    int X = 1;
 
    // Iterating from 1 to N and storing
    // consecutive odd integers at odd
    // indices and twice of element at
    // previous index at even indices
    for (int i = 1; i <= N; i++) {
        if (i % 2 == 1) {
            ans[i] = X;
        }
        else {
            ans[i] = 2 * ans[i - 1];
            X += 2;
        }
    }
 
    // Printing the array
    for (int i = 1; i <= N; i++) {
        System.out.print(ans[i] + " ");
    }
}
 
// Driver Code
    public static void main (String[] args) {
         int N = 7;
            constructArray(N);
    }
}
 
// This code is contributed by hrithikgarg03188.

# Python Code for above approach
 
# Function to find an array such
# that elements at even positions
# are divisible by their previous
# element and elements at odd positions
# are not
def constructArray(N):
 
    # Declaring array A to store the answer
    ans = [0 for i in range(N + 1)]
 
    # Initializing a variable X by 1
    X = 1
 
    # Iterating from 1 to N and storing
    # consecutive odd integers at odd
    # indices and twice of element at
    # previous index at even indices
    for i in range(1, N + 1):
        if (i % 2 == 1):
            ans[i] = X
        else:
            ans[i] = 2 * ans[i - 1]
            X += 2
 
    # Printing the array
    for i in range(1, N + 1):
        print(ans[i],end = " ")
 
# Driver Code
N = 7
constructArray(N)
 
# This code is contributed by shinjanpatra

using System;
using System.Collections.Generic;
public class GFG {
 
  // Function to find an array such
  // that elements at even positions
  // are divisible by their previous
  // element and elements at odd positions
  // are not
  static void constructArray(int N)
  {
    // Declaring array A to store the answer
    int[] ans = new int[N + 1];
 
    // Initializing a variable X by 1
    int X = 1;
 
    // Iterating from 1 to N and storing
    // consecutive odd integers at odd
    // indices and twice of element at
    // previous index at even indices
    for (int i = 1; i <= N; i++) {
      if (i % 2 == 1) {
        ans[i] = X;
      }
      else {
        ans[i] = 2 * ans[i - 1];
        X += 2;
      }
    }
 
    // Printing the array
    for (int i = 1; i <= N; i++) {
      Console.Write(ans[i] + " ");
    }
  }
  static public void Main()
  {
    int N = 7;
    constructArray(N);
 
  }
}
 
// This code is contributed by phasing17

<script>
    // JavaScript Code for above approach
 
    // Function to find an array such
    // that elements at even positions
    // are divisible by their previous
    // element and elements at odd positions
    // are not
    const constructArray = (N) => {
     
        // Declaring array A to store the answer
        let ans = new Array(N + 1).fill(0);
 
        // Initializing a variable X by 1
        let X = 1;
 
        // Iterating from 1 to N and storing
        // consecutive odd integers at odd
        // indices and twice of element at
        // previous index at even indices
        for (let i = 1; i <= N; i++) {
            if (i % 2 == 1) {
                ans[i] = X;
            }
            else {
                ans[i] = 2 * ans[i - 1];
                X += 2;
            }
        }
 
        // Printing the array
        for (let i = 1; i <= N; i++) {
            document.write(`${ans[i]} `);
        }
    }
 
    // Driver Code
    let N = 7;
    constructArray(N);
 
// This code is contributed by rakeshsahni
</script>

1 2 3 6 5 10 7 

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