Sum of all duck numbers mendacity in vary [L,R] for Q queries

0
6


Given Q queries within the type of a 2D array arr[][] through which each row consists of two numbers L and R which denotes a variety [L, R], the duty is to seek out the sum of all duck numbers mendacity within the given vary [L, R].

A duck quantity is a quantity that has not less than one 0 current in it.

Examples:

Enter: Q = 2, arr[] = {{1, 13}, {99, 121}}
Output: {10, 1275}
Rationalization: In first question {1, 13}, solely quantity with 0 in it’s 10. 
So the sum is 10.
In Second question {99, 121}, the numbers with 0 in them are 
100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 120. 
So their sum is 1275

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

 

Method: To resolve the issue observe the beneath concept:

Use prefix array to retailer the sum of the numbers from 1 to a selected index having 0 in them.This fashion  every question will be answered in O(1) .

Comply with the steps to unravel this downside:

  • Initialize the pre[] array to retailer the prefix sum.
  • Iterate from 1 to a sure huge worth (say 105, we are able to additionally repair this to be the utmost among the many queries): 
    • If i has 0, then pre[i] = pre[i – 1] + i ;
    • In any other case, pre[i] = pre[i – 1];   
  • The reply to the question for vary L to R is (pre[R] – pre[L – 1])

Beneath is the implementation of the above strategy:

C++14

  

#embrace <bits/stdc++.h>

utilizing namespace std;

  

int pre[100001];

  

bool CheckZero(int x)

{

    string s = to_string(x);

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

  

    

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

        i++;

  

    

    whereas (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 major()

{

    int Q = 5;

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

                     { 99, 121 },

                     { 56, 70 },

                     { 1000, 1111 },

                     { 108, 250 } };

  

    

    printsumduck(arr, Q);

    return 0;

}

Output

10
1275
130
117105
4762

Time Complexity: O(max(Q, N)) the place N is the utmost worth until which precomputation is being completed. 
Auxiliary House: O(N)

LEAVE A REPLY

Please enter your comment!
Please enter your name here