- 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 an integer range starting from the variable let's say start till the variable end and a variable k and the task is to calculate the count of numbers in the range such that the numbers don't have more than 'k' non-zero digits.

**Input -** int start = 50, end = 100 and K = 2;

**Output -** Count of Numbers in Range where the number does not contain more than K non zero digits are: 50

**Explanation -** The range is starting from 50 to 100 and we are given k as 2. As we can see, all the numbers between 50 and 100 have 2-digits numbers which makes it impossible to contain more than 2 zero digits except the number 100 which is a 3-digit number but it will also have 2 zero's not more than that therefore the count is 50.

**Input -** int start = 50, end = 100 and K = 1;

**Output -** Count of Numbers in Range where the number does not contain more than K non zero

digits are: 5

**Explanation -** The range is starting from 50 to 100 and we are given k as 1. As we can see, all the numbers between 50 and 100 have 2-digits numbers so the numbers with not more than 1 or k as non-zero digits are 50, 60, 70, 80 and 90 therefore the count is 5.

- Create a range of integer numbers starting from the variable start till the variable end and declare the k and input the value. Pass the data to the function for further processing.
- Create a variable of type vector let's say vec.
- Start loop while till the value which is the value inside the variable start. Now, inside the while push the value as val % 10 to the vector and set val as val / 10.
- Call the reverse function in STL by passing vec.begin() and vec.end() as an argument to it.
- Set the values in the array as -1 using memset.
- Return the check_val(0, 0, 0, vec) which is a function that will check whether the digits are non-zero's or not.
- Inside the check_val function-:
- Check IF place equals to size of a vector then check IF temp <= k then return 1 or return 0.
- Check IF arr[place][temp][set_val] not equals to -1 then return the value at arr[place][temp][set_val].
- Declare the variable to store the result and set it to 0.
- Declare a variable val and set it to 9 IF set_val equals 1 ELSE set it to i++
- Start loop FOR from 0 till the value val
- Inside the loop set temp_2 as temp and check IF 1 not equals 0 then increment the value of temp_2 by 1 and set temp_3 as set_val and check i less than vec[place] then set temp_3 as 1
- Set the value of count as the recursive call to the function check_val(place + 1, temp_2, temp_3, vec)
- Return arr[place][temp][set_val] equals count.

#include <bits/stdc++.h> using namespace std; int arr[20][20][2]; int K; int check_val(int place, int temp, int set_val, vector < int > vec) { if (place == vec.size()) { if (temp <= K) { return 1; } return 0; } if (arr[place][temp][set_val] != -1) { return arr[place][temp][set_val]; } int count = 0; int val = (set_val ? 9 : vec[place]); for (int i = 0; i <= val; i++) { int temp_2 = temp; if (i != 0) { temp_2++; } int temp_3 = set_val; if (i < vec[place]) { temp_3 = 1; } count += check_val(place + 1, temp_2, temp_3, vec); } return arr[place][temp][set_val] = count; } int Not_more_k(int val) { vector < int > vec; while (val) { vec.push_back(val % 10); val = val / 10; } reverse(vec.begin(), vec.end()); memset(arr, -1, sizeof(arr)); return check_val(0, 0, 0, vec); } int main() { int start = 50, end = 100; K = 2; int count = Not_more_k(end) - Not_more_k(start); cout << "Count of Numbers in Range where the number does not contain more than K non zero digits are: " << count; return 0; }

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

Count of Numbers in Range where the number does not contain more than K non zero digits are: 50

- Related Questions & Answers
- Count numbers in range that are divisible by all of its non-zero digits in C++
- Count of numbers between range having only non-zero digits whose sum of digits is N and number is divisible by M in C++
- Program to find number not greater than n where all digits are non-decreasing in python
- Count of Numbers in a Range where digit d occurs exactly K times in C++
- Count of Numbers such that difference between the number and sum of its digits not less than L in C++
- Count of Numbers in Range where first digit is equal to last digit of the number in C++
- Count numbers with unit digit k in given range in C++
- Total number of non-decreasing numbers with n digits
- Adding digits of a number using more than 2 methods JavaScript
- Count the number of words having sum of ASCII values less than and greater than k in C++
- Count of sub-strings that do not contain all the in C++
- Count all the numbers in a range with smallest factor as K in C++
- Count of numbers from range[L, R] whose sum of digits is Y in C++
- Count the number of non-increasing subarrays in C++
- Program to find out the number of non-zero submatrices in C++

Advertisements