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

Given Q queries within the type of a 2D array arr[][] during 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 at the very least one 0 current in it.

Examples:

Enter: Q = 2, arr[] = {{1, 13}, {99, 121}}
Output: {10, 1275}
Clarification: 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}

Strategy: To resolve the issue comply with the beneath thought:

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

Observe the steps to resolve this downside:

• Initialize the pre[] array to retailer the prefix sum.
• Iterate from 1 to a sure large worth (say 10⁵, 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]). 

Under is the implementation of the above method:

10
1275
130
117105
4762

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