Modifique la array reemplazando cada elemento con la potencia más cercana de GCD de todos los elementos anteriores

Dada una array arr[] que consta de N enteros positivos, la tarea es reemplazar cada elemento de la array con la potencia de GCD más cercana de todos los elementos de la array anteriores. Si existe más de una respuesta posible, imprima cualquiera de ellas.

Ejemplos:

Entrada: arr[] = {4, 2, 8, 2}
Salida: 4 1 8 2
Explicación: 
 Para el elemento arr[0], el elemento sigue siendo el mismo.
Para el elemento arr[1], el MCD de los elementos anteriores es 4. La potencia de 4 más cercana a 2 es 1.
Para el elemento arr[2], la MCD de los elementos anteriores es 2. La potencia de 2 más cercana a 8 es 8.
Para el elemento arr[3], el MCD de los elementos anteriores es 2. La potencia de 2 que está más cerca de 2 es 2.
Por lo tanto, la array modificada se convierte en {4, 1, 8, 2}.

Entrada: arr[] = {3, 6, 9, 2}
Salida: 3 9 9 3

Enfoque: el problema dado se puede resolver calculando el prefijo GCD y luego encontrando la potencia más cercana de ese GCD que está más cerca del elemento actual, para cada elemento de la array. A continuación se presentan algunas observaciones:

• Para calcular la potencia de X que está más cerca de Y , la idea es obtener el valor de K tal que la diferencia absoluta entre X ^K e Y sea mínima.
• Para encontrar el valor de K , encuentre el valor mínimo de log _x (Y) .
• Por lo tanto, K y (K + 1) serán los dos números enteros para los cuales la potencia más cercana puede ser un valor posible.

Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos prefixGCD con arr[0] , para almacenar el prefijo GCD hasta cada índice de la array.
• Recorra la array dada arr[] sobre el rango de índices [1, N] y realice los siguientes pasos:
  • Encuentre el valor mínimo de log _prefixGCD (arr[i]) , digamos K .
  • Encuentre el valor de (arr[i] ^K ) y (arr[i] ^{K + 1} ) y verifique cuál está más cerca de arr[i] y asigne ese valor al índice actual de la array.
  • Actualice prefixGCD como el gcd de prefixGCD y arr[i] .
• Después de completar los pasos anteriores, imprima la array modificada.

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

// CPP program for the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to find the float
// value of log function
int log1(int x, int base)
{
  return int(log(x) / log(base));
}
 
// Function for finding the nearest
// power of X with respect to Y
int getNP(int x, int y)
{
 
  // Base Case
  if (y == 1)
    return 1;
 
  // Find the value of K
  int k = int(log1(x, y));
 
  // Nearest power of GCD closest to Y
  if (abs(pow(y, k) - x) < abs(pow(y, (k + 1)) - x))
    return pow(y, k);
  return pow(y, (k + 1));
 
}
 
 
// Function to modify the given array
// such that each array element is the
// nearest power of X with respect to Y
vector<int> modifyEle(vector<int> arr)
{
  int prevGCD = arr[0];
 
  // Traverse the array
  for (int i = 1; i < arr.size(); i++)
  {
 
    // Find the current number
    int NP = getNP(arr[i], prevGCD);
 
    // Update the GCD
    prevGCD = __gcd(arr[i], prevGCD);
 
    // Update the array at the
    // current index
    arr[i] = NP;
  }
 
  // Return the updated GCD array
  return arr;
 
}
 
// Driver Code
int main()
{
  vector<int>arr{4, 2, 8, 2};
 
  // Function Call
  vector<int> ans = modifyEle(arr);
  cout<<"[";
  for(int i = 0; i < ans.size(); i++)
    if(i < ans.size() - 1)
      cout << ans[i] << ", ";
  else
    cout << ans[i];
  cout << "]";
}
 
// This code is contributed by SURENDRA_GANGWAR.

// Java program for the above approach
import java.util.*;
class GFG
{
 
    // gcd
    static int gcd(int x, int y)
    {
        if (x == 0)
            return y;
        return gcd(y % x, x);
    }
 
    // Function to find the float
    // value of log function
    static int log1(int x, int b)
    {
        return (int)(Math.log(x) / Math.log(b));
    }
 
    // Function for finding the nearest
    // power of X with respect to Y
    static int getNP(int x, int y)
    {
 
        // Base Case
        if (y == 1)
            return 1;
 
        // Find the value of K
        int k = (int)(log1(x, y));
 
        // Nearest power of GCD closest to Y
        if (Math.abs(Math.pow(y, k) - x)
            < Math.abs(Math.pow(y, (k + 1)) - x))
            return (int)(Math.pow(y, k));
        return (int)(Math.pow(y, (k + 1)));
    }
 
    // Function to modify the given array
    // such that each array element is the
    // nearest power of X with respect to Y
    static ArrayList<Integer> modifyEle(ArrayList<Integer> arr)
    {
        int prevGCD = arr.get(0);
 
        // Traverse the array
        for (int i = 1; i < arr.size(); i++) {
 
            // Find the current number
            int NP = getNP(arr.get(i), prevGCD);
 
            // Update the GCD
            prevGCD = gcd(arr.get(i), prevGCD);
 
            // Update the array at the
            // current index
            arr.set(i, NP);
        }
 
        // Return the updated GCD array
        return arr;
    }
 
// Driver Code
public static void main(String[] args)
{
    ArrayList<Integer> arr = new ArrayList<Integer>() ;
    arr.add(4);
    arr.add(2);
    arr.add(8);
    arr.add(2);
 
        // Function Call
        ArrayList<Integer> ans = new ArrayList<Integer>();
        ans = modifyEle(arr);
        System.out.print("[");
        for (int i = 0; i < ans.size(); i++)
            if (i < ans.size() - 1)
                System.out.print(ans.get(i) + ", ");
            else
                System.out.print(ans.get(i));
       System.out.print("]");
}
}
 
// This code is contributed by susmitakundugoaldanga.

# Python program for the above approach
 
import math
 
# Function to find the float
# value of log function
def LOG(x, base):
    return int(math.log(x)/math.log(base))
 
# Function for finding the nearest
# power of X with respect to Y
def getNP(x, y):
 
    # Base Case
    if y == 1:
        return 1
 
    # Find the value of K
    k = int(math.log(x, y))
 
    # Nearest power of GCD closest to Y
    if abs(y**k - x) < abs(y**(k + 1) - x):
        return y**k
 
    return y**(k + 1)
 
# Function to find the GCD of a and b
def GCD(a, b):
   
      # Base Case
    if b == 0:
        return a
       
    # Recursively calculate GCD
    return GCD(b, a % b)
 
# Function to modify the given array
# such that each array element is the
# nearest power of X with respect to Y
def modifyEle(arr):
   
      # Stores the prefix GCD
    prevGCD = arr[0]
     
    # Traverse the array
    for i in range(1, len(arr)):
       
          # Find the current number
        NP = getNP(arr[i], prevGCD)
 
        # Update the GCD
        prevGCD = GCD(arr[i], prevGCD)
         
        # Update the array at the
        # current index
        arr[i] = NP
         
    # Return the updated GCD array
    return arr
 
 
# Driver Code
arr = [4, 2, 8, 2]
 
# Function Call
print(modifyEle(arr))

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
    // gcd
    static int gcd(int x, int y)
    {
        if (x == 0)
            return y;
        return gcd(y % x, x);
    }
 
    // Function to find the float
    // value of log function
    static int log1(int x, int b)
    {
        return (int)(Math.Log(x) / Math.Log(b));
    }
 
    // Function for finding the nearest
    // power of X with respect to Y
    static int getNP(int x, int y)
    {
 
        // Base Case
        if (y == 1)
            return 1;
 
        // Find the value of K
        int k = (int)(log1(x, y));
 
        // Nearest power of GCD closest to Y
        if (Math.Abs(Math.Pow(y, k) - x)
            < Math.Abs(Math.Pow(y, (k + 1)) - x))
            return (int)(Math.Pow(y, k));
        return (int)(Math.Pow(y, (k + 1)));
    }
 
    // Function to modify the given array
    // such that each array element is the
    // nearest power of X with respect to Y
    static List<int> modifyEle(List<int> arr)
    {
        int prevGCD = arr[0];
 
        // Traverse the array
        for (int i = 1; i < arr.Count; i++) {
 
            // Find the current number
            int NP = getNP(arr[i], prevGCD);
 
            // Update the GCD
            prevGCD = gcd(arr[i], prevGCD);
 
            // Update the array at the
            // current index
            arr[i] = NP;
        }
 
        // Return the updated GCD array
        return arr;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        List<int> arr = new List<int>() { 4, 2, 8, 2 };
 
        // Function Call
        List<int> ans = new List<int>();
        ans = modifyEle(arr);
        Console.Write("[");
        for (int i = 0; i < ans.Count; i++)
            if (i < ans.Count - 1)
                Console.Write(ans[i] + ", ");
            else
                Console.Write(ans[i]);
        Console.Write("]");
    }
}
 
// This code is contributed by chitranayal.

<script>
      // JavaScript program for the above approach
      // gcd
      function gcd(x, y) {
        if (x === 0)
            return y;
        return gcd(y % x, x);
      }
 
      // Function to find the float
      // value of log function
      function log1(x, b) {
        return parseInt(Math.log(x) / Math.log(b));
      }
 
      // Function for finding the nearest
      // power of X with respect to Y
      function getNP(x, y) {
        // Base Case
        if (y === 1) return 1;
 
        // Find the value of K
        var k = parseInt(log1(x, y));
 
        // Nearest power of GCD closest to Y
        if (Math.abs(Math.pow(y, k) - x) <
            Math.abs(Math.pow(y, k + 1) - x))
            return parseInt(Math.pow(y, k));
        return parseInt(Math.pow(y, k + 1));
      }
 
      // Function to modify the given array
      // such that each array element is the
      // nearest power of X with respect to Y
      function modifyEle(arr) {
          var prevGCD = arr[0];
 
        // Traverse the array
        for (var i = 1; i < arr.length; i++) {
          // Find the current number
          var NP = getNP(arr[i], prevGCD);
 
          // Update the GCD
          prevGCD = gcd(arr[i], prevGCD);
 
          // Update the array at the
          // current index
          arr[i] = NP;
        }
 
        // Return the updated GCD array
        return arr;
      }
 
      // Driver Code
      var arr = [4, 2, 8, 2];
 
      // Function Call
      var ans = [];
      ans = modifyEle(arr);
      document.write("[");
      for (var i = 0; i < ans.length; i++)
          if (i < ans.length - 1)
            document.write(ans[i] + ", ");
        else
            document.write(ans[i]);
      document.write("]");
</script>

[4, 1, 8, 2]

Complejidad temporal: O(N*log(M)), donde M es el elemento máximo del arreglo . 
Espacio Auxiliar: O(1)