# 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 ` `utilizing` `namespace` `std;` ` `  `int` `pre;` ` `  `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[], ``int` `Q)` `{` ` `  `    ` `    ``precompute();` `    ``for` `(``int` `i = 0; i < Q; i++) {` ` `  `        ` `        ``printresult(arr[i], arr[i]);` `    ``}` `}` ` `  `int` `major()` `{` `    ``int` `Q = 5;` `    ``int` `arr[] = { { 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)