Recursive program to print all numbers less than N which consist of digits 1 or 3 only
Given an integer N, the task is to print all the numbers ? N which have their digits as only 1 or 3.
Examples:
Input: N = 10
Output: 3 1Input: N = 20
Output: 13 11 3 1
Approach:
- First, check if the number is greater than 0. If yes then proceed further, else program is terminated.
- Check for the presence of digits 1 or 3 at each place of the number.
- If we find 1 or 3 at every place of the number then print the number. Now, check for the next number by using a recursive call for a number one less than the current number.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <iostream> using namespace std; // Recursive function to print the desired numbers void printNumbers( int N) { // Bool variable to track whether each digit of // the number fulfills the given condition bool flag = 1; // Creating a copy of the number int x = N; // Checking if the number has a positive value if (N > 0) { // Loop to iterate through digits // of the number until every digit // fulfills the given condition while (x > 0 && flag == 1) { // Get last digit int digit = x % 10; // Updating value of flag to be 0 if // the digit is neither 1 nor 3 if (digit != 1 && digit != 3) flag = 0; // Eliminate last digit x = x / 10; } // If N consists of digits 1 or 3 only if (flag == 1) cout << N << " " ; // Recursive call for the next number printNumbers(N - 1); } } // Driver code int main() { int N = 20; printNumbers(N); return 0; } |
Java
// Java implementation of the above approach class GFG { // Recursive function to print the desired numbers static void printNumbers( int N) { // flag variable to track whether each digit of // the number fulfills the given condition int flag = 1 ; // Creating a copy of the number int x = N; // Checking if the number has a positive value if (N > 0 ) { // Loop to iterate through digits // of the number until every digit // fulfills the given condition while (x > 0 && flag == 1 ) { // Get last digit int digit = x % 10 ; // Updating value of flag to be 0 if // the digit is neither 1 nor 3 if (digit != 1 && digit != 3 ) { flag = 0 ; } // Eliminate last digit x = x / 10 ; } // If N consists of digits 1 or 3 only if (flag == 1 ) { System.out.print(N + " " ); } // Recursive call for the next number printNumbers(N - 1 ); } } // Driver code public static void main(String[] args) { int N = 20 ; printNumbers(N); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python 3 implementation of the approach # Recursive function to print the # desired numbers def printNumbers(N): # Bool variable to track whether each digit # of the number fulfills the given condition flag = 1 # Creating a copy of the number x = N # Checking if the number has a # positive value if (N > 0 ): # Loop to iterate through digits # of the number until every digit # fulfills the given condition while (x > 0 and flag = = 1 ): # Get last digit digit = x % 10 # Updating value of flag to be 0 if # the digit is neither 1 nor 3 if (digit ! = 1 and digit ! = 3 ): flag = 0 # Eliminate last digit x = x / / 10 # If N consists of digits 1 or 3 only if (flag = = 1 ): print (N, end = " " ) # Recursive call for the next number printNumbers(N - 1 ) # Driver code if __name__ = = '__main__' : N = 20 printNumbers(N) # This code is contributed by # Surendra_Gangwar |
C#
// C# implementation of the above approach using System; class GFG { // Recursive function to print the desired numbers static void printNumbers( int N) { // flag variable to track whether each digit of // the number fulfills the given condition int flag = 1; // Creating a copy of the number int x = N; // Checking if the number has a positive value if (N > 0) { // Loop to iterate through digits // of the number until every digit // fulfills the given condition while (x > 0 && flag == 1) { // Get last digit int digit = x % 10; // Updating value of flag to be 0 if // the digit is neither 1 nor 3 if (digit != 1 && digit != 3) flag = 0; // Eliminate last digit x = x / 10; } // If N consists of digits 1 or 3 only if (flag == 1) Console.Write(N + " " ); // Recursive call for the next number printNumbers(N - 1); } } // Driver code public static void Main() { int N = 20; printNumbers(N); } } // This code is contributed by Ryuga |
PHP
<?php // PHP implementation of the above approach // Recursive function to print the // desired numbers function printNumbers( $N ) { // Bool variable to track whether each // digit of the number fulfills the // given condition $flag = 1; // Creating a copy of the number $x = $N ; // Checking if the number has a // positive value if ( $N > 0) { // Loop to iterate through digits // of the number until every digit // fulfills the given condition while ((int) $x > 0 && $flag == 1) { // Get last digit $digit = $x % 10; // Updating value of flag to be 0 // if the digit is neither 1 nor 3 if ( $digit != 1 && $digit != 3) $flag = 0; // Eliminate last digit $x = $x / 10; } // If N consists of digits 1 or 3 only if ( $flag == 1) { echo $N ; echo " " ; } // Recursive call for the next number printNumbers( $N - 1); } } // Driver code $N = 20; printNumbers( $N ); // This code is contributed // by Arnab Kundu ?> |
Javascript
<script> // JavaScript implementation of the above approach // Recursive function to print the desired numbers function printNumbers(N) { // flag variable to track whether each digit of // the number fulfills the given condition let flag = 1; // Creating a copy of the number let x = N; // Checking if the number has a positive value if (N > 0) { // Loop to iterate through digits // of the number until every digit // fulfills the given condition while (x > 0 && flag == 1) { // Get last digit let digit = x % 10; // Updating value of flag to be 0 if // the digit is neither 1 nor 3 if (digit != 1 && digit != 3) flag = 0; // Eliminate last digit x = parseInt(x / 10, 10); } // If N consists of digits 1 or 3 only if (flag == 1) document.write(N + " " ); // Recursive call for the next number printNumbers(N - 1); } } let N = 20; printNumbers(N); </script> |
Output:
13 11 3 1
Time complexity: O(N*logN)
Auxiliary space: O(N) for recursive stack space.
Note that the idea of this post to explain a recursive solution there exist a better approach to solve this problem. We can use queue to solve this efficiently. Please refer Count of Binary Digit numbers smaller than N for details of efficient approach.