Given Q queries in the form of a 2D array arr[][] in which every row consists of two numbers L and R which denotes a range [L, R], the task is to find the sum of all duck numbers lying in the given range [L, R].
A duck number is a number that has at least one 0 present in it.
Examples:
Input: Q = 2, arr[] = {{1, 13}, {99, 121}}
Output: {10, 1275}
Explanation: In first query {1, 13}, only number with 0 in it is 10.
So the sum is 10.
In Second query {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 1275Input: Q = 5, arr[] = {{1, 10}, {99, 121}, {56, 70}, {1000, 1111}, {108, 250}}
Output: {10, 1275, 130, 117105, 4762}
Approach: To solve the problem follow the below idea:
Use prefix array to store the sum of the numbers from 1 to a particular index having 0 in them.This way each query can be answered in O(1) .
Follow the steps to solve this problem:
- Initialize the pre[] array to store the prefix sum.
- Iterate from 1 to a certain big value (say 105, we can also fix this to be the maximum among the queries):
- If i has 0, then pre[i] = pre[i – 1] + i ;
- Otherwise, pre[i] = pre[i – 1];
- The answer to the query for range L to R is (pre[R] – pre[L – 1]).
Below is the implementation of the above approach:
C++14
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;int pre[100001];// Function to check duck numbersbool CheckZero(int x){ string s = to_string(x); int i = 0, n = s.size(); // To check leading zeros while (i < n && s[i] == '0') i++; // Check remaining digits while (i < n) { if (s[i] == '0') return true; i++; } return false;}// Function to precompute sum of// duck numbers from 1 to ivoid precompute(){ for (int i = 1; i < 100001; i++) { if (CheckZero(i)) pre[i] = pre[i - 1] + i; else pre[i] = pre[i - 1]; }}// Function to print sum of duck numbers// in range [L, R]void printresult(int L, int R){ cout << pre[R] - pre[L - 1] << endl;}void printsumduck(int arr[][2], int Q){ // To calculate pre array precompute(); for (int i = 0; i < Q; i++) { // arr[i][0] is L and arr[i][1] is R printresult(arr[i][0], arr[i][1]); }}// Driver Codeint main(){ int Q = 5; int arr[][2] = { { 1, 10 }, { 99, 121 }, { 56, 70 }, { 1000, 1111 }, { 108, 250 } }; // Function call printsumduck(arr, Q); return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { static int[] pre= new int[100001]; // Function to check duck numbers static boolean CheckZero(int x) { String s = String.valueOf(x); int i = 0, n = s.length(); // To check leading zeros while (i < n && s.charAt(i)== '0') i++; // Check remaining digits while (i < n) { if (s.charAt(i) == '0') return true; i++; } return false; } // Function to precompute sum of // duck numbers from 1 to i static void precompute() { for (int i = 1; i < 100001; i++) { if (CheckZero(i)) pre[i] = pre[i - 1] + i; else pre[i] = pre[i - 1]; } } // Function to print sum of duck numbers // in range [L, R] static void printresult(int L, int R) { System.out.println(pre[R] - pre[L - 1]); } static void printsumduck(int [][]arr, int Q) { // To calculate pre array precompute(); for (int i = 0; i < Q; i++) { // arr[i][0] is L and arr[i][1] is R printresult(arr[i][0], arr[i][1]); } } // Driver Code public static void main (String[] args) { int Q = 5; int [][] arr = { { 1, 10 }, { 99, 121 }, { 56, 70 }, { 1000, 1111 }, { 108, 250 } }; // Function call printsumduck(arr, Q); }}// This code is contributed by hrithikgarg03188. |
Python3
# Python code to implement the above approachpre = [0]*(100001)def CheckZero(x): s = str(x) i = 0 n = len(s) # To check leading zero while(i < n and s[i] == '0'): i += 1 # Check remaining digits while(i < n): if(s[i] == '0'): return True i += 1 return False# Function to precompute sum of duck numbers from 1 to idef precompute(): for i in range(1, 100001): if(CheckZero(i)): pre[i] = pre[i-1]+i else: pre[i] = pre[i-1]# Function to print sum of duck numbers in range [L, R]def printresult(L, R): print(pre[R] - pre[L-1])def printsumduck(arr, Q): # To calculate pre array precompute() for i in range(Q): # arr[i][0] is L and arr[i][1] is R printresult(arr[i][0], arr[i][1])Q = 5arr = [[1, 10], [99, 121], [56, 70], [1000, 1111], [108, 250]]# Function callprintsumduck(arr, Q)# This code is contributed by lokeshmvs21. |
C#
// C# code to implement the approachusing System;class GFG { static int[] pre= new int[100001]; // Function to check duck numbers static bool CheckZero(int x) { string s = x.ToString(); int i = 0, n = s.Length; // To check leading zeros while (i < n && s[i]== '0') i++; // Check remaining digits while (i < n) { if (s[i] == '0') return true; i++; } return false; } // Function to precompute sum of // duck numbers from 1 to i static void precompute() { for (int i = 1; i < 100001; i++) { if (CheckZero(i)) pre[i] = pre[i - 1] + i; else pre[i] = pre[i - 1]; } } // Function to print sum of duck numbers // in range [L, R] static void printresult(int L, int R) { Console.WriteLine(pre[R] - pre[L - 1]); } static void printsumduck(int [,]arr, int Q) { // To calculate pre array precompute(); for (int i = 0; i < Q; i++) { // arr[i][0] is L and arr[i][1] is R printresult(arr[i, 0], arr[i, 1]); } }// Driver Codepublic static void Main(){ int Q = 5; int [,] arr = { { 1, 10 }, { 99, 121 }, { 56, 70 }, { 1000, 1111 }, { 108, 250 } }; // Function call printsumduck(arr, Q);}}// This code is contributed by code_hunt. |
Javascript
<script> // JavaScript code to implement the approach let pre = new Array(100001).fill(0); // Function to check duck numbers const CheckZero = (x) => { let s = x.toString(); let i = 0, n = s.length; // To check leading zeros while (i < n && s[i] == '0') i++; // Check remaining digits while (i < n) { if (s[i] == '0') return true; i++; } return false; } // Function to precompute sum of // duck numbers from 1 to i const precompute = () => { for (let i = 1; i < 100001; i++) { if (CheckZero(i)) pre[i] = pre[i - 1] + i; else pre[i] = pre[i - 1]; } } // Function to print sum of duck numbers // in range [L, R] const printresult = (L, R) => { document.write(`${pre[R] - pre[L - 1]}<br/>`); } const printsumduck = (arr, Q) => { // To calculate pre array precompute(); for (let i = 0; i < Q; i++) { // arr[i][0] is L and arr[i][1] is R printresult(arr[i][0], arr[i][1]); } } // Driver Code let Q = 5; let arr = [[1, 10], [99, 121], [56, 70], [1000, 1111], [108, 250]]; // Function call printsumduck(arr, Q); // This code is contributed by rakeshsahni</script> |
Output
10 1275 130 117105 4762
Time Complexity: O(max(Q, N)) where N is the maximum value till which precomputation is being done.
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
