Dada una array arr[] que consta de N enteros positivos y una array 2D queries[][] del tipo {a, K, X} tal que si el valor de a es 1 , entonces multiplique los primeros K elementos de la array por X. De lo contrario, multiplique los últimos elementos de la array K por X . La tarea es calcular el GCD de la array después de realizar cada consulta en la array original.
Ejemplos:
Entrada: arr[] = {2, 3, 4, 8}, Consultas[][3] = {{1, 2, 2}, {2, 4, 5}}
Salida: 2 5
Explicación:
Consulta 1: El la consulta dada es {1, 2, 2}. Después de multiplicar los 2 primeros elementos de la array por 2, arr[] se modifica a {4, 6, 4, 8}. GCD de la array modificada es 2.
Consulta 2: la consulta dada es {2, 4, 5}. Después de multiplicar los últimos 4 elementos de la array por 5, arr[] se modifica a {10, 15, 20, 40}. GCD de la array actualizada es 5.Entrada: arr[] = {4, 12, 4, 9}, Consultas[][3] = {{1, 3, 3}, {2, 4, 1}}
Salida: 3 1
Enfoque ingenuo: el enfoque más simple es actualizar la array dada realizando cada consulta y luego encontrar el GCD de la array actualizada .
Complejidad temporal: O(N * Q * log(M)), donde M es el elemento máximo presente en el arreglo.
Espacio Auxiliar: O(N)
Enfoque eficiente: el enfoque anterior se puede optimizar almacenando las arrays GCD de prefijo y sufijo de la array dada y resolviendo cada consulta en tiempo O (1) siguiendo los pasos a continuación:
- Inicialice un prefijo [] y sufijo [] de array de tamaño N para almacenar las arrays GCD de prefijo y sufijo de la array dada.
- Recorra la array desde el frente y la parte posterior y encuentre el prefijo y el sufijo GCD en cada índice y guárdelo en prefijo [] y sufijo [] respectivamente.
- Ahora, recorra la array consultas[] y para cada consulta {a, K, X} realice lo siguiente:
- Si el valor de K es N , imprima el valor de prefijo [N – 1] * X como resultado.
- Si el valor de a es 1, encuentre el MCD del prefijo [K – 1] * X y el sufijo [K] como resultado del prefijo [K – 1] * X es el nuevo MCD de los primeros K números y el sufijo [ K + 1] es el GCD de los elementos restantes de la array.
- Si el valor de a es 2, encuentre el MCD del prefijo [N – K – 1] y el sufijo [N – K] * X como resultado como el prefijo [N – K – 1] * X es el nuevo MCD de los primeros K números y el sufijo [N – K] es el GCD de los elementos restantes de la array.
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;
// Function to find the GCD after performing
// each query on array elements
void findGCDQueries(int arr[], int N,
int Queries[][3],
int Q)
{
// Stores prefix array and suffix
// array
int prefix[N], suffix[N];
prefix[0] = arr[0];
suffix[N - 1] = arr[N - 1];
// Build prefix array
for (int i = 1; i < N; i++) {
prefix[i] = __gcd(prefix[i - 1],
arr[i]);
}
// Build suffix array
for (int i = N - 2; i >= 0; i--) {
suffix[i] = __gcd(suffix[i + 1],
arr[i]);
}
// Traverse queries array
for (int i = 0; i < Q; i++) {
int a = Queries[i][0];
int K = Queries[i][1];
int X = Queries[i][2];
// Edge Case when update is
// is required till the end
if (K == N) {
cout << prefix[N - 1] * X;
continue;
}
// Edge Case when update is
// is required till the front
if (a == 1) {
cout << __gcd(prefix[K - 1] * X,
suffix[K]);
}
// Find the resultant operation
// for each query
else {
cout << __gcd(suffix[N - K] * X,
prefix[N - K - 1]);
}
cout << " ";
}
}
// Driver Code
int main()
{
int arr[] = { 2, 3, 4, 8 };
int N = sizeof(arr) / sizeof(arr[0]);
int Queries[][3] = {
{ 1, 2, 2 },
{ 2, 4, 5 }
};
int Q = sizeof(Queries)
/ sizeof(Queries[0]);
findGCDQueries(arr, N, Queries, Q);
return 0;
}
Java
// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG
{
// Recursive function to return gcd of a and b
static int gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return gcd(a - b, b);
return gcd(a, b - a);
}
// Function to find the GCD after performing
// each query on array elements
static void findGCDQueries(int arr[], int N,
int Queries[][],
int Q)
{
// Stores prefix array and suffix
// array
int prefix[] = new int[N], suffix[] = new int[N];
prefix[0] = arr[0];
suffix[N - 1] = arr[N - 1];
// Build prefix array
for (int i = 1; i < N; i++) {
prefix[i] = gcd(prefix[i - 1],
arr[i]);
}
// Build suffix array
for (int i = N - 2; i >= 0; i--) {
suffix[i] = gcd(suffix[i + 1],
arr[i]);
}
// Traverse queries array
for (int i = 0; i < Q; i++) {
int a = Queries[i][0];
int K = Queries[i][1];
int X = Queries[i][2];
// Edge Case when update is
// is required till the end
if (K == N) {
System.out.print(prefix[N - 1] * X);
continue;
}
// Edge Case when update is
// is required till the front
if (a == 1) {
System.out.print(gcd(prefix[K - 1] * X,
suffix[K]));
}
// Find the resultant operation
// for each query
else {
System.out.print(gcd(suffix[N - K] * X,
prefix[N - K - 1]));
}
System.out.print(" ");
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 3, 4, 8 };
int N = arr.length;
int Queries[][] = {
{ 1, 2, 2 },
{ 2, 4, 5 }
};
int Q = Queries.length;
findGCDQueries(arr, N, Queries, Q);
}
}
// This code is contributed by sanjoy_62.
Python3
# Python 3 program for the above approach from math import gcd # Function to find the GCD after performing # each query on array elements def findGCDQueries(arr, N, Queries, Q): # Stores prefix array and suffix # array prefix = [0 for i in range(N)] suffix = [0 for i in range(N)] prefix[0] = arr[0] suffix[N - 1] = arr[N - 1] # Build prefix array for i in range(1,N,1): prefix[i] = gcd(prefix[i - 1], arr[i]) # Build suffix array i = N - 2 while(i>= 0): suffix[i] = gcd(suffix[i + 1], arr[i]) i -= 1 # Traverse queries array for i in range(Q): a = Queries[i][0] K = Queries[i][1] X = Queries[i][2] # Edge Case when update is # is required till the end if (K == N): print(prefix[N - 1] * X,end = " ") continue # Edge Case when update is # is required till the front if (a == 1): print(gcd(prefix[K - 1] * X,suffix[K]),end = " ") # Find the resultant operation # for each query else: print(gcd(suffix[N - K] * X, prefix[N - K - 1]),end = " ") # Driver Code if __name__ == '__main__': arr = [2, 3, 4, 8] N = len(arr) Queries = [[1, 2, 2], [2, 4, 5]] Q = len(Queries) findGCDQueries(arr, N, Queries, Q) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program to implement
// the above approach
using System;
public class GFG
{
// Recursive function to return gcd of a and b
static int gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return gcd(a - b, b);
return gcd(a, b - a);
}
// Function to find the GCD after performing
// each query on array elements
static void findGCDQueries(int []arr, int N,
int [,]Queries,
int Q)
{
// Stores prefix array and suffix
// array
int []prefix = new int[N];
int []suffix = new int[N];
prefix[0] = arr[0];
suffix[N - 1] = arr[N - 1];
// Build prefix array
for (int i = 1; i < N; i++) {
prefix[i] = gcd(prefix[i - 1],
arr[i]);
}
// Build suffix array
for (int i = N - 2; i >= 0; i--) {
suffix[i] = gcd(suffix[i + 1],
arr[i]);
}
// Traverse queries array
for (int i = 0; i < Q; i++) {
int a = Queries[i,0];
int K = Queries[i,1];
int X = Queries[i,2];
// Edge Case when update is
// is required till the end
if (K == N) {
Console.Write(prefix[N - 1] * X);
continue;
}
// Edge Case when update is
// is required till the front
if (a == 1) {
Console.Write(gcd(prefix[K - 1] * X,
suffix[K]));
}
// Find the resultant operation
// for each query
else {
Console.Write(gcd(suffix[N - K] * X,
prefix[N - K - 1]));
}
Console.Write(" ");
}
}
// Driver Code
public static void Main(string[] args)
{
int []arr = { 2, 3, 4, 8 };
int N = arr.Length;
int [,]Queries = {
{ 1, 2, 2 },
{ 2, 4, 5 }
};
int Q = Queries.GetLength(0);
findGCDQueries(arr, N, Queries, Q);
}
}
// This code is contributed by AnkThon.
Javascript
<script>
// JavaScript program to implement the above approach
// Recursive function to return gcd of a and b
function gcd(a, b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return gcd(a - b, b);
return gcd(a, b - a);
}
// Function to find the GCD after performing
// each query on array elements
function findGCDQueries(arr, N, Queries, Q)
{
// Stores prefix array and suffix
// array
let prefix = new Array(N), suffix = new Array(N);
prefix[0] = arr[0];
suffix[N - 1] = arr[N - 1];
// Build prefix array
for (let i = 1; i < N; i++) {
prefix[i] = gcd(prefix[i - 1],
arr[i]);
}
// Build suffix array
for (let i = N - 2; i >= 0; i--) {
suffix[i] = gcd(suffix[i + 1],
arr[i]);
}
// Traverse queries array
for (let i = 0; i < Q; i++) {
let a = Queries[i][0];
let K = Queries[i][1];
let X = Queries[i][2];
// Edge Case when update is
// is required till the end
if (K == N) {
document.write(prefix[N - 1] * X);
continue;
}
// Edge Case when update is
// is required till the front
if (a == 1) {
document.write(gcd(prefix[K - 1] * X,
suffix[K]));
}
// Find the resultant operation
// for each query
else {
document.write(gcd(suffix[N - K] * X,
prefix[N - K - 1]));
}
document.write(" ");
}
}
let arr = [ 2, 3, 4, 8 ];
let N = arr.length;
let Queries = [
[ 1, 2, 2 ],
[ 2, 4, 5 ]
];
let Q = Queries.length;
findGCDQueries(arr, N, Queries, Q);
</script>
Producción
2 5
Complejidad temporal: O((N + Q)* log M), donde M es el elemento máximo del arreglo.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kartikey134 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA