There will be a weekly contest this Sunday on the Leetcode platform. The tourist aka Gennady Korotkevich is preparing the problem statements for the contest. He thoughts of a problem namely the count of numbers from the range [L, R] whose sum of digits is Y. Let us discuss the problem statement and the various approaches to solve the problem.

Problem Statement

Given two numbers â€˜Lâ€™ and â€˜Râ€™, we need to find the count of numbers between L and R, the the the whose sum of digits is â€˜Yâ€™.

For Example:

L=10, R=100, Y=7

Then the numbers whose sum of digits is 7 and lies between L and R are:

16 25 34 43 52 61 70

So there are 7 such numbers. Therefore the output is 7.

This is the brute force approach. The algorithm is as follows:

Iterate from i = L to i = R.

Initialize the answer as 0.

Calculate the sum of digits of â€˜iâ€™.

If the sum of digits is equal to â€˜Yâ€™, increment the answer.

Return answer.

Now let us implement it in the C++ programming language.

Program

#include<iostream> usingnamespace std; boolcheck(int x, int y){ int sum=0; // Calculating sum of digits of x. while(x>0){ sum+=x%10; x/=10; }

// Checking if sum of digits is equal to y. return (sum==y); } inthelper(int L, int R, int Y){ int answer = 0;

// Iterating from L to R. for(int i=L; i<=R; i++){

// Checking if sum of digits of i is equal to Y. if(check(i,Y)){

// If yes, increment the answer. answer++; } } return answer; } intmain(){ int L, R, Y; cin>>L>>R>>Y; cout<<helper(L, R, Y); return 0; }

Input

10 100 7

Output

7

Time Complexity

O((R - L) * log(R))

We are iterating from L and R and checking if the sum of digits of the iterator is equal to Y or not. The checking function takes O(log(R)) time in the worst case. The number is reduced to 1 by repeatedly dividing by 10. So it takes O( log(R) ) time.

Space Complexity

O(1)

We are only declaring a fixed number of variables. So it takes constant space.

inthelper(string str, int i, int sum, int tight,int dp[N][N][2]) { // Check if count of digits in a number is // greater than count of digits in str if (i >= str.size() || sum < 0) {

// If sum of digits of a // number is equal to Y if (sum == 0) { return 1; }

return 0; }

// Check if current subproblem has // already been computed if (dp[sum][i][tight] != -1) { return dp[sum][i][tight]; }

// Stores count of numbers whose // sum of digits is Y int ans = 0;

// Check if the number // exceeds Y or not int end = tight ? str[i] - '0' : 9;

// Iterate over all possible // values of i-th digits for (int j = 0; j <= end; j++) {

// Update ans ans += helper(str, i + 1, sum - j, (tight & (j == end)), dp); }

// Return ans return dp[sum][i][tight]=ans; }

intcount(int L, int R, int Y) { if (R == 0 && Y == 0) {

return 1; }

// Stores numbers in the form // of its equivalent string string str = to_string(R);

// Stores overlapping subproblems int dp[N][N][2];

In this blog, we learned about a new problem namely the Count of numbers from the range [L, R] whose sum of digits is Y. We solved it using two different methods. The first method is Brute force and gives a time complexity of O((R - L+1) * log(R)). Second approach used dynamic programming and gave a time complexity of O(Y * log(R)). Stay tuned for more such problems.

Happy Coding!

Live masterclass

Land an SDE Role at Google: Master DSA the smart way

by Saurav Prateek, SDE2@Google

19 Sep, 2024

01:30 PM

Become a Data Analyst at MAANG: Learn PowerBI for Data visualization

by Megna Roy, Senior Data Analyst @Amazon

17 Sep, 2024

01:30 PM

Learn Advanced Excel: Ace Data Analytics Interview

by Megna Roy, Data Analyst @ Amazon

15 Sep, 2024

06:30 AM

Land an SDE Role at Google: Master DSA the smart way

by Saurav Prateek, SDE2@Google

19 Sep, 2024

01:30 PM

Become a Data Analyst at MAANG: Learn PowerBI for Data visualization