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 1275Enter: 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 10^{5}, 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

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)