Saltar al contenido

Suma de todos los números de patos dentro del rango [L,R] para consultas Q

Dado q consultas en forma de matriz 2D Arr[][] en el que cada fila consta de dos números yo y R que indica un rango [L, R]la tarea es encontrar la suma de todos los números de patos que están en el rango especificado [L, R].

Un número de pato es un número que contiene al menos un 0.

Ejemplos:

Aporte: Q = 2, arr[] = {{1, 13}, {99, 121}}
Salida: {10, 1275}
Explicación: En la primera consulta {1, 13}, solo el número con 0 es 10.
Entonces la suma es 10.
En la segunda búsqueda {99, 121} los números con 0 en ellos son
100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 120.
entonces su suma es 1275

Aporte: Q = 5, arr[] = {{1, 10}, {99, 121}, {56, 70}, {1000, 1111}, {108, 250}}
Salida: {10, 1275, 130, 117105, 4762}

Acercarse: Siga la siguiente idea para resolver el problema:

Use una matriz de prefijos para almacenar la suma de números de 1 a algún índice con 0 en él. De esta manera, cualquier pregunta puede responderse en O(1) .

Siga los pasos para resolver este problema:

  • Inicializar el pre[] matriz para almacenar la suma del prefijo.
  • Repita desde 1 hasta cierto valor grande (digamos 105también podemos resolver esto como el máximo entre las preguntas):
    • si i tiene 0, entonces pre[i] = anterior[i – 1] + yo;
    • Otro, pre[i] = anterior[i – 1];
  • La respuesta a la pregunta del alcance. yo Hasta que R es (pre[R] – pre[L – 1]).

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

C++14

 

#include <bits/stdc++.h>

using namespace std;

 

int pre[100001];

 

bool CheckZero(int x)

{

    string s = to_string(x);

    int i = 0, n = s.size();

 

    

    while (i < n && s[i] == '0')

        i++;

 

    

    while (i < n) {

        if (s[i] == '0')

            return true;

        i++;

    }

 

    return false;

}

 

void precompute()

{

    for (int i = 1; i < 100001; i++) {

        if (CheckZero(i))

            pre[i] = pre[i - 1] + i;

        else

            pre[i] = pre[i - 1];

    }

}

 

void printresult(int L, int R)

{

    cout << pre[R] - pre[L - 1] << endl;

}

 

void printsumduck(int arr[][2], int Q)

{

 

    

    precompute();

    for (int i = 0; i < Q; i++) {

 

        

        printresult(arr[i][0], arr[i][1]);

    }

}

 

int main()

{

    int Q = 5;

    int arr[][2] = { { 1, 10 },

                     { 99, 121 },

                     { 56, 70 },

                     { 1000, 1111 },

                     { 108, 250 } };

 

    

    printsumduck(arr, Q);

    return 0;

}

Salida:

10
1275
130
117105
4762

Complejidad del tiempo: O(max(Q, N)) donde N es el valor máximo hasta el cual se realiza el cálculo previo.
cuarto auxiliar: A)