Esta es una pregunta de consulta de rango en la que se nos ha proporcionado una array de tamaño N. Hay 3 tipos de consultas y debe responder un número M de consultas específicas.
- Consulta de tipo 1: se le darán 3 valores en forma de LRX y en este tipo de consulta tendrá que multiplicar x a los elementos de la array inclusive en el rango L a R.
- Consulta de tipo 2: en esta consulta también se le darán 3 valores en forma de LRY y después de ejecutar este tipo de consulta, reemplazará los elementos de la array en la forma en que el primer elemento se reemplaza por Y, el segundo elemento se reemplaza por 2*Y y como sigue inclusive en el rango L a R.
- Consulta de tipo 3: en esta se le darán 2 valores L y R y en esta debe
encontrar el producto de todos los números en el rango. Como este número podría ser muy grande, solo tiene que encontrar el número de ceros finales de este número cuando se representa en notación decimal.
Ejemplos:
Input : arr[] = {2, 4, 3, 5, 5|
queries[] = {{3 2 4}, {3 2 5}, {2 2 4 1},
{1 3 3 10}, {3 1 5}}
Output : 5
Explanation :
Since the first query is of type 3 so we multiply
the elements 4 * 3 * 5 = 60.
Since the second query is of type 3 so we multiply
the elements 4 * 3 * 5 * 5 = 300.
Since the third query is of type 2 and the value of
Y is 1 so after execution of this query the array
becomes [2, 1, 2, 3, 5].
Since the fourth query is of type 1 and the value of
x is 10 so after execution of this query the array
becomes [2, 1, 20, 3, 5].
Now the last query is of type 3 then we simply multiply
all the elements inclusive in the given range i.e.
2 * 1 * 20 * 3 * 5 = 600.
Now our task is to calculate the trailing zeros obtained
in the type 3 query i.e. 60 has 1 trailing zero, 300 has
2 trailing zeros and 600 has 2 trailing zeros so the
answer of this given input is 5.
Método 1: En esto podemos simplemente aplicar el método de fuerza bruta. En el método de fuerza bruta, aplicaremos toda la operación en los elementos de la array y para cada consulta de tipo 3 almacenaremos el resultado obtenido en una nueva array, luego calcularemos el número de ceros finales para cada resultado obtenido y luego calcularemos el deseado. suma.
La complejidad de este método será O(m*n) ya que operaremos todo el arreglo m veces para las m consultas dadas y se requerirá un espacio extra de tamaño m para guardar los resultados obtenidos en las consultas tipo 3 para calcular el número de ceros finales después de la ejecución de m consultas.
Entonces, la complejidad del tiempo es O(m*n) y la complejidad del espacio es O(m).
Método 2: en este método tenemos 2 vectores porque un número con cero final puede ser múltiplo de 10 y 10 es un múltiplo de 2 y 5, por lo que se han mantenido dos vectores separados para este propósito. Y el resto se ha explicado a continuación.
Implementación:
C++
// C++ program to solve three types of queries.
#include <bits/stdc++.h>
using namespace std;
//vector of 1000 elements,
//all set to 0
vector<int> twos(1000,0);
//vector of 1000 elements,
//all set to 0
vector<int> fives(1000,0);
int sum = 0;
// Function to check number of
// trailing zeros in multiple of 2
int returnTwos(int val)
{
int count = 0;
while (val % 2 == 0 && val != 0) {
val = val / 2;
count++;
}
return count;
}
// Function to check number of
// trailing zeros in multiple of 5
int returnFives(int val)
{
int count = 0;
while (val % 5 == 0 && val != 0) {
val = val / 5;
count++;
}
return count;
}
// Function to solve the queries received
void solve_queries(int arr[], int n)
{
int type, ql, qr, x, y;
cin >> type;
// If the query is of type 1.
if (type == 1) {
cin >> ql >> qr >> x;
// Counting the number of
// zeros in the given value of x
int temp = returnTwos(x);
int temp1 = returnFives(x);
for (int i = ql - 1; i < qr; i++) {
// The value x has been multiplied
// to their respective indices
arr[i] = arr[i] * x;
// The value obtained above has been
// added to their respective vectors
twos[i] += temp;
fives[i] += temp1;
}
}
// If the query is of type 2.
if (type == 2) {
cin >> ql >> qr >> y;
// Counting the number of
// zero in the given value of x
int temp = returnTwos(y);
int temp1 = returnFives(y);
for (int i = ql - 1; i < qr; i++) {
// The value y has been replaced
// to their respective indices
arr[i] = (i - ql + 2) * y;
// The value obtained above has been
// added to their respective vectors
twos[i] = returnTwos(i - ql + 2) + temp;
fives[i] = returnFives(i - ql + 2) + temp1;
}
}
// If the query is of type 2
if (type == 3) {
cin >> ql >> qr;
int sumtwos = 0;
int sumfives = 0;
for (int i = ql - 1; i < qr; i++) {
// as the number of trailing zeros for
// each case has been found for each array
// element then we simply add those to
// the respective index to a variable
sumtwos += twos[i];
sumfives += fives[i];
}
// Compare the number of zeros
// obtained in the multiples of five and two
// consider the minimum of them and add them
sum += min(sumtwos, sumfives);
}
}
// Driver code
int main()
{
int n, m;
// Input the Size of array
// and number of queries
cin >> n >> m;
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
twos[i] = returnTwos(arr[i]);
fives[i] = returnFives(arr[i]);
}
// Running the while loop
// for m number of queries
while (m--) {
solve_queries(arr, n);
}
cout << sum << endl;
return 0;
}
Java
// Java program to solve three types of queries.
import java.io.*;
import java.util.*;
import java.util.Arrays;
class GFG{
static Scanner sc= new Scanner(System.in);
// Vector of 1000 elements,
// all set to 0
static int twos[] = new int[1000];
// Vector of 1000 elements,
// all set to 0
static int fives[] = new int[1000];
static int sum = 0;
// Function to check number of
// trailing zeros in multiple of 2
static int returnTwos(int val)
{
int count = 0;
while (val % 2 == 0 && val != 0)
{
val = val / 2;
count++;
}
return count;
}
// Function to check number of
// trailing zeros in multiple of 5
static int returnFives(int val)
{
int count = 0;
while (val % 5 == 0 && val != 0)
{
val = val / 5;
count++;
}
return count;
}
// Function to solve the queries received
static void solve_queries(int arr[], int n)
{
int type = sc.nextInt();
// If the query is of type 1.
if (type == 1)
{
int ql = sc.nextInt();
int qr = sc.nextInt();
int x = sc.nextInt();
// Counting the number of
// zeros in the given value of x
int temp = returnTwos(x);
int temp1 = returnFives(x);
for(int i = ql - 1; i < qr; i++)
{
// The value x has been multiplied
// to their respective indices
arr[i] = arr[i] * x;
// The value obtained above has been
// added to their respective vectors
twos[i] += temp;
fives[i] += temp1;
}
}
// If the query is of type 2.
if (type == 2)
{
int ql = sc.nextInt();
int qr = sc.nextInt();
int y = sc.nextInt();
// Counting the number of
// zero in the given value of x
int temp = returnTwos(y);
int temp1 = returnFives(y);
for(int i = ql - 1; i < qr; i++)
{
// The value y has been replaced
// to their respective indices
arr[i] = (i - ql + 2) * y;
// The value obtained above has been
// added to their respective vectors
twos[i] = returnTwos(i - ql + 2) + temp;
fives[i] = returnFives(i - ql + 2) + temp1;
}
}
// If the query is of type 2
if (type == 3)
{
int ql = sc.nextInt();
int qr = sc.nextInt();
int sumtwos = 0;
int sumfives = 0;
for(int i = ql - 1; i < qr; i++)
{
// As the number of trailing zeros for
// each case has been found for each array
// element then we simply add those to
// the respective index to a variable
sumtwos += twos[i];
sumfives += fives[i];
}
// Compare the number of zeros
// obtained in the multiples of five and two
// consider the minimum of them and add them
sum += Math.min(sumtwos, sumfives);
}
}
// Driver code
public static void main(String[] args)
{
// Input the Size of array
// and number of queries
int n = sc.nextInt();
int m = sc.nextInt();
int arr[] = new int[n];
for(int i = 0; i < n; i++)
{
arr[i] = sc.nextInt();
twos[i] = returnTwos(arr[i]);
fives[i] = returnFives(arr[i]);
}
// Running the while loop
// for m number of queries
while (m-- != 0)
{
solve_queries(arr, n);
}
System.out.println(sum);
}
}
// This code is contributed by SHUBHAMSINGH10
Python3
# Python3 program to solve three types of queries. # vector of 1000 elements, # all set to 0 twos = [0] * 1000 # vector of 1000 elements, # all set to 0 fives = [0] * 1000 sum = 0 # Function to check number of # trailing zeros in multiple of 2 def returnTwos(val): count = 0 while (val % 2 == 0 and val != 0): val = val // 2 count += 1 return count # Function to check number of # trailing zeros in multiple of 5 def returnFives(val): count = 0 while (val % 5 == 0 and val != 0): val = val // 5 count += 1 return count # Function to solve the queries received def solve_queries(arr, n): global sum arrr1 = list(map(int,input().split())) type = arrr1[0] # If the query is of type 1. if (type == 1): ql, qr, x = arrr1[1], arrr1[2], arrr1[3] # Counting the number of # zeros in the given value of x temp = returnTwos(x) temp1 = returnFives(x) i = ql - 1 while(i < qr): # The value x has been multiplied # to their respective indices arr[i] = arr[i] * x # The value obtained above has been # added to their respective vectors twos[i] += temp fives[i] += temp1 i += 1 # If the query is of type 2. if (type == 2): ql, qr, y = arrr1[1], arrr1[2], arrr1[3] # Counting the number of # zero in the given value of x temp = returnTwos(y) temp1 = returnFives(y) i = ql - 1 while(i < qr): # The value y has been replaced # to their respective indices arr[i] = (i - ql + 2) * y # The value obtained above has been # added to their respective vectors twos[i] = returnTwos(i - ql + 2) + temp fives[i] = returnFives(i - ql + 2) + temp1 i += 1 # If the query is of type 2 if (type == 3): ql, qr = arrr1[1], arrr1[2] sumtwos = 0 sumfives = 0 i = ql - 1 while(i < qr): # As the number of trailing zeros for # each case has been found for each array # element then we simply add those to # the respective index to a variable sumtwos += twos[i] sumfives += fives[i] i += 1 # Compare the number of zeros # obtained in the multiples of five and two # consider the minimum of them and add them sum += min(sumtwos, sumfives) # Driver code # Input the Size of array # and number of queries n, m = map(int, input().split()) arr = list(map(int, input().split())) for i in range(n): twos[i] = returnTwos(arr[i]) fives[i] = returnFives(arr[i]) # Running the while loop # for m number of queries while (m): m -= 1 solve_queries(arr, n) print(sum) # This code is contributed by SHUBHAMSINGH10
C#
// C# program to solve three types of queries.
using System;
public class HelloWorld
{
// Array of 1000 elements,
// all set to 0
static int[] twos=new int[1000];
// Array of 1000 elements,
// all set to 0
static int[] fives=new int[1000];
static int sum = 0;
// Function to check number of
// trailing zeros in multiple of 2
static int returnTwos(int val)
{
int count = 0;
while (val % 2 == 0 && val != 0) {
val = val / 2;
count++;
}
return count;
}
// Function to check number of
// trailing zeros in multiple of 5
static int returnFives(int val)
{
int count = 0;
while (val % 5 == 0 && val != 0) {
val = val / 5;
count++;
}
return count;
}
// Function to solve the queries received
static void solve_queries(int []arr, int n)
{
int type, ql, qr, x, y;
type = Convert.ToInt32(Console.ReadLine());
// If the query is of type 1.
if (type == 1) {
ql = Convert.ToInt32(Console.ReadLine());
qr = Convert.ToInt32(Console.ReadLine());
x = Convert.ToInt32(Console.ReadLine());
// Counting the number of
// zeros in the given value of x
int temp = returnTwos(x);
int temp1 = returnFives(x);
for (int i = ql - 1; i < qr; i++) {
// The value x has been multiplied
// to their respective indices
arr[i] = arr[i] * x;
// The value obtained above has been
// added to their respective vectors
twos[i] += temp;
fives[i] += temp1;
}
}
// If the query is of type 2.
if (type == 2) {
ql = Convert.ToInt32(Console.ReadLine());
qr = Convert.ToInt32(Console.ReadLine());
y = Convert.ToInt32(Console.ReadLine());
// Counting the number of
// zero in the given value of x
int temp = returnTwos(y);
int temp1 = returnFives(y);
for (int i = ql - 1; i < qr; i++) {
// The value y has been replaced
// to their respective indices
arr[i] = (i - ql + 2) * y;
// The value obtained above has been
// added to their respective vectors
twos[i] = returnTwos(i - ql + 2) + temp;
fives[i] = returnFives(i - ql + 2) + temp1;
}
}
// If the query is of type 3
if (type == 3) {
ql = Convert.ToInt32(Console.ReadLine());
qr = Convert.ToInt32(Console.ReadLine());
int sumtwos = 0;
int sumfives = 0;
for (int i = ql - 1; i < qr; i++) {
// as the number of trailing zeros for
// each case has been found for each array
// element then we simply add those to
// the respective index to a variable
sumtwos += twos[i];
sumfives += fives[i];
}
// Compare the number of zeros
// obtained in the multiples of five and two
// consider the minimum of them and add them
sum += Math.Min(sumtwos, sumfives);
}
}
public static void Main(string[] args)
{
int n=5, m=5;
int[] arr = { 2, 4, 3, 5, 5 };
for (int i = 0; i < 1000; i++)
{
twos[i] = 0;
fives[i] = 0;
}
for (int i = 0; i < n; i++) {
twos[i] = returnTwos(arr[i]);
fives[i] = returnFives(arr[i]);
}
// Running the while loop
// for m number of queries
while (m > 0) {
solve_queries(arr, n);
m=m-1;
}
Console.WriteLine(sum);
}
}
// This code is contributed by Aarti_Rathi
Javascript
<script>
//vector of 1000 elements,
//all set to 0
let twos = [];
//vector of 1000 elements,
//all set to 0
let fives = [];
let sum = 0;
// Function to check number of
// trailing zeros in multiple of 2
function returnTwos(val)
{
let count = 0;
while (val % 2 == 0 && val != 0) {
val = val / 2;
count++;
}
return count;
}
// Function to check number of
// trailing zeros in multiple of 5
function returnFives(val)
{
var count = 0;
while (val % 5 == 0 && val != 0) {
val = val / 5;
count++;
}
return count;
}
// Function to solve the queries received
function solve_queries(arr, n)
{
var type, ql, qr, x, y;
type = prompt();
// If the query is of type 1.
if (type == 1) {
ql = prompt();
qr = prompt();
x = prompt();
// Counting the number of
// zeros in the given value of x
var temp = returnTwos(x);
var temp1 = returnFives(x);
for (var i = ql - 1; i < qr; i++) {
// The value x has been multiplied
// to their respective indices
arr[i] = arr[i] * x;
// The value obtained above has been
// added to their respective vectors
twos[i] += temp;
fives[i] += temp1;
}
}
// If the query is of type 2.
if (type == 2) {
ql = prompt();
qr = prompt();
y = prompt();
// Counting the number of
// zero in the given value of x
var temp = returnTwos(y);
var temp1 = returnFives(y);
for (var i = ql - 1; i < qr; i++) {
// The value y has been replaced
// to their respective indices
arr[i] = (i - ql + 2) * y;
// The value obtained above has been
// added to their respective vectors
twos[i] = returnTwos(i - ql + 2) + temp;
fives[i] = returnFives(i - ql + 2) + temp1;
}
}
// If the query is of type 2
if (type == 3) {
ql = prompt();
qr = prompt();
var sumtwos = 0;
var sumfives = 0;
for (var i = ql - 1; i < qr; i++) {
// as the number of trailing zeros for
// each case has been found for each array
// element then we simply add those to
// the respective index to a variable
sumtwos += twos[i];
sumfives += fives[i];
}
// Compare the number of zeros
// obtained in the multiples of five and two
// consider the minimum of them and add them
sum += Math.min(sumtwos, sumfives);
}
}
// This code is contributed by Aarti_Rathi
// Driver code
var n = prompt();
var m = prompt();
var arr = [];
for(var i=0; i<n; i++)
{
arr[i] = prompt();
twos[i] = returnTwos(arr[i]);
fives[i] = returnFives(arr[i]);
}
// Running the while loop
// for m number of queries
while (m--) {
solve_queries(arr, n);
}
document.write(sum)
// This code is contributed by Aarti_Rathi
</script>
Producción
0
Complejidad temporal: O(n*qlogn).
Espacio auxiliar: O(1).
Para cada consulta, toma O (nlogn), por lo que la complejidad de tiempo final es O (n * q)
Este artículo es una contribución de Mohak Agrawal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA