- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

We are given a number N and another number L. The goal is to find the numbers between 1 and N that have a difference between the number itself and the sum of its digits is not less than L.

If N=23, L=10 then the count of such numbers will be 4.

23-(2+3)=18, 22-(2+2)=18, 21-(2+1)=18, 20-(2+0)=18.

All above numbers meet the condition

But 19-(1+9)=9 which is less than L, similarly 18,17….1.

Let us understand with examples

**Input** − N=30 L=19

**Output** − Count of Numbers such that difference between the number and sum of its digits not less than L are − 1

**Explanation** − Only 30 meets the condition, 30-(3+0)=27 > 19

**Input** − N=123330 L=5466

**Output** − Count of Numbers such that difference between the number and sum of its digits not less than L are − 6841

Using binary search we will find the first number that meets the condition. If that number is num then the condition will also be true for num+1 and so on.

If any current mid value satisfies the condition then all numbers between mid and end will also satisfy this condition so we can simply add end-mid+1 to count.

Take num and L as long variables.

Function Digit_sum(LL num) takes a number num and returns the sum of its digits.

Take initial sum as total=0.

Using a while loop, add reminder num%10 to total and reduce num by 10. Do this until num>0.

Return total as sum of digits of num.

Function Less_than_L(LL num, LL L) takes a number num and a number L and returns count of Numbers such that difference between the number and sum of its digits not less than L

Take the initial count as 0.

Implement binary search using while loop where start=1 and end=num.

Calculate middle number as temp=(start+end)/2.

If the difference between temp and sum of digits of temp is not less than L then all numbers greater than temp will also satisfy the same condition.

Count of such numbers including temp will be num-temp+1. Add this to count. And set end=temp-1.

Otherwise set start=temp+1.

At the end of binary search count will have numbers with difference between them and sum of digits not less than L

Return count as result.

#include <bits/stdc++.h> using namespace std; typedef long long LL; int Digit_sum(LL num){ LL total = 0; while (num > 0){ total += num % 10; num = num/10; z} return total; } LL Less_than_L(LL num, LL L){ LL count = 0; LL start = 1; LL end = num; while (start <= end){ LL temp = (end + start) / 2; LL temp_2 = temp - Digit_sum(temp); if (temp_2 >= L){ count = num - temp + 1; end = temp - 1; } else{ start = temp + 1; } } return count; } int main(){ LL num = 234516; LL L = 235; cout<<"Count of Numbers such that difference between the number and sum of its digits not less than L are: "<< Less_than_L(num, L); return 0; }

If we run the above code it will generate the following output −

Count of Numbers such that difference between the number and sum of its digits not less than L are: 234267

- Related Questions & Answers
- Count numbers with difference between number and its digit sum greater than specific value in C++
- Print a number strictly less than a given number such that all its digits are distinct in C++
- Count the number of words having sum of ASCII values less than and greater than k in C++
- Count of numbers from range[L, R] whose sum of digits is Y in C++
- Find a number x such that sum of x and its digits is equal to given n in C++
- Maximum subarray size, such that all subarrays of that size have sum less than k in C++
- Find a number x such that sum of x and its digits is equal to given n using C++.
- Maximum subarray size, such that all subarrays of that size have sum less than k in C++ program
- Find maximum N such that the sum of square of first N natural numbers is not more than X in C++
- Find maximum number of elements such that their absolute difference is less than or equal to 1 in C++
- Difference between product and sum of digits of a number in JavaScript
- Count the number of pairs that have column sum greater than row sum in C++
- Count of Numbers in Range where the number does not contain more than K non zero digits in C++
- Count of all even numbers in the range [L, R] whose sum of digits is divisible by 3 in C++
- Find maximum N such that the sum of square of first N natural numbers is not more than X in Python

Advertisements