Print all Good numbers in given range in C++

In this problem, we are given three values L, R, and d. Our task is to print all good numbers within the range L to R that do not contain the d as its digit.

A good number is a number in which every digit is larger than the sum of digits of its right (all less significant bits than it). For example, 732 is a good number, 7> 3+2 and 3>2.

Now, let’s take an example to understand the problem,

Input: L = 400 , R = 500 , k = 3 Output: 410, 420, 421

Explanation − good numbers between 400 to 500 are −

410, 420, 421, 430, but we cannot use 3 so 430 is not printed.

To solve this problem, for this we will check all numbers within the given range i.e. L to R, if a number is a good number and any of its digits is not equal to k, then print it otherwise leave it.

Check for Good number − we will traverse the number from right to left, and maintain a sum, at any point if the sum is greater than the next number return false.

Example

Let’s see the program to illustrate the below algorithm −

 Live Demo

#include<bits/stdc++.h> using namespace std; bool isvalidNumber(int n, int d){    int digit = n%10;    int sum = digit;    if (digit == d)       return false;    n /= 10;    while (n){       digit = n%10;       if (digit == d || digit <= sum)          return false;       else{          sum += digit;          n /= 10;       }    }    return 1; } void printGoodNumbersLtoR(int L, int R, int d){    for (int i=L; i<=R; i++){       if (isvalidNumber(i, d))          cout << i << " ";    } } int main(){    int L = 400, R = 600, d = 3;    cout<<"All good numbers from "<<L<<" to "<<R<<" that do not contain "<<d<<" are :\n";    printGoodNumbersLtoR(L, R, d);    return 0; }

Output

All good numbers from 400 to 600 that do not contain 3 are − 410 420 421 510 520 521 540