Find the n-th number made of even digits only
Given a number n, find out the n-th positive number made up of even digits (0, 2, 4, 6, 8) only. First few numbers made of even digits are 0, 2, 4, 6, 8, 20, 22, 24…….
Examples :
Input : 2 Output : 2 Second number made of 0, 2, 4, 6, 8 is 2 Input : 10 Output : 28
Naive Approach
A naive approach is to start from 0 and checking if it is made of only {0, 2, 4, 6, 8} and stop when you find n-th such number.
C++
// Simple C++ program to find // n-th number made of even // digits only #include<bits/stdc++.h> using namespace std; // function to calculate nth // number made of even digits only int findNthEvenDigitNumber( int n ) { // variable to note how // many such numbers have // been found till now int count = 0; for ( int i = 0 ; ; i++) { int curr = i; // bool variable to check if // 1, 3, 5, 7, 9 is there or not bool isCurrEvenDigit = true ; // checking each digit // of the number while (curr != 0) { // If 1, 3, 5, 7, 9 is found // temp is changed to false if (curr % 10 == 1 || curr % 10 == 3 || curr % 10 == 5 || curr % 10 == 7 || curr % 10 == 9) isCurrEvenDigit = false ; curr = curr / 10; } // temp is true it means that it // does not have 1, 3, 5, 7, 9 if (isCurrEvenDigit == true ) count++; // If nth such number is // found return it if (count == n) return i; } } // Driver Code int main() { cout << findNthEvenDigitNumber(2) << endl; cout << findNthEvenDigitNumber(10) << endl; return 0; } |
Java
// Simple Java program to // find the n-th number made // of even digits only class GFG { // function to calculate nth // number made of even digits only static int findNthEvenDigitNumber( int n ) { // variable to note how // many such numbers have // been found till now int count = 0 ; for ( int i = 0 ; ; i++) { int curr = i; // bool variable to check if // 1, 3, 5, 7, 9 is there or not boolean isCurrEvenDigit = true ; // checking each digit // of the number while (curr != 0 ) { // If 1, 3, 5, 7, 9 is found // temp is changed to false if (curr % 10 == 1 || curr % 10 == 3 || curr % 10 == 5 || curr % 10 == 7 || curr % 10 == 9 ) isCurrEvenDigit = false ; curr = curr / 10 ; } // temp is true it means that it // does not have 1, 3, 5, 7, 9 if (isCurrEvenDigit == true ) count++; // If nth such number // is found return it if (count == n) return i; } } // Driver Code public static void main (String[] args) { System.out.println(findNthEvenDigitNumber( 2 )); System.out.println(findNthEvenDigitNumber( 10 )); } } |
Python3
# Simple Python3 program to find nth # number made of even digits only # function to calculate nth number # made of even digits only def findNthEvenDigitNumber(n): # variable to note how many such # numbers have been found till now count = 0 ; i = 0 ; while ( True ): curr = i; # bool variable to check if # 1, 3, 5, 7, 9 is there or not isCurrEvenDigit = True ; # checking each digit of the number while (curr ! = 0 ): # If 1, 3, 5, 7, 9 is found # temp is changed to false if (curr % 10 = = 1 or curr % 10 = = 3 or curr % 10 = = 5 or curr % 10 = = 7 or curr % 10 = = 9 ): isCurrEvenDigit = False ; curr = curr / / 10 ; # temp is true it means that it # does not have 1, 3, 5, 7, 9 if (isCurrEvenDigit = = True ): count + = 1 ; # If nth such number is found, # return it if (count = = n): return i; i + = 1 ; # Driver Code print (findNthEvenDigitNumber( 2 )); print (findNthEvenDigitNumber( 10 )); # This code is contributed by mits |
C#
// Simple C# program to // find the n-th number // made of even digits only using System; class GFG { // function to calculate nth // number made of even digits only static int findNthEvenDigitNumber( int n ) { // variable to note how // many such numbers have // been found till now int count = 0; for ( int i = 0 ; ; i++) { int curr = i; // bool variable to check if // 1, 3, 5, 7, 9 is there or not bool isCurrEvenDigit = true ; // checking each digit // of the number while (curr != 0) { // If 1, 3, 5, 7, 9 is found // temp is changed to false if (curr % 10 == 1 || curr % 10 == 3 || curr % 10 == 5 || curr % 10 == 7 || curr % 10 == 9 ) isCurrEvenDigit = false ; curr = curr / 10; } // temp is true it means that it // does not have 1, 3, 5, 7, 9 if (isCurrEvenDigit == true ) count++; // If nth such number // is found return it if (count == n) return i; } } // Driver code public static void Main () { Console.WriteLine(findNthEvenDigitNumber(2)); Console.WriteLine(findNthEvenDigitNumber(10)); } } // |
PHP
<?php // Simple C++ program to find // nth number made of even // digits only // function to calculate nth // number made of even digits only function findNthEvenDigitNumber( $n ) { // variable to note how // many such numbers have // been found till now $count = 0; for ( $i = 0 ; ; $i ++) { $curr = $i ; // bool variable to check if // 1, 3, 5, 7, 9 is there or not $isCurrEvenDigit = true ; // checking each digit // of the number while ( $curr != 0) { // If 1, 3, 5, 7, 9 is found // temp is changed to false if ( $curr % 10 == 1 || $curr % 10 == 3 || $curr % 10 == 5 || $curr % 10 == 7 || $curr % 10 == 9) $isCurrEvenDigit = false; $curr = $curr / 10; } // temp is true it means that it // does not have 1, 3, 5, 7, 9 if ( $isCurrEvenDigit == true) $count ++; // If nth such number // is found return it if ( $count == $n ) return $i ; } } // Driver Code echo findNthEvenDigitNumber(2), "\n" ; echo findNthEvenDigitNumber(10) ; // This code is contributed by nitin mittal ?> |
Javascript
<script> // Simple JavaScript program to find // n-th number made of even // digits only // Function to calculate nth // number made of even digits only function findNthEvenDigitNumber(n) { // Variable to note how // many such numbers have // been found till now let count = 0; for (let i = 0;; i++) { let curr = i; // Bool variable to check if // 1, 3, 5, 7, 9 is there or not let isCurrEvenDigit = true ; // Checking each digit // of the number while (curr != 0) { // If 1, 3, 5, 7, 9 is found // temp is changed to false if (curr % 10 == 1 || curr % 10 == 3 || curr % 10 == 5 || curr % 10 == 7 || curr % 10 == 9) isCurrEvenDigit = false ; curr = Math.floor(curr / 10); } // temp is true it means that it // does not have 1, 3, 5, 7, 9 if (isCurrEvenDigit === true ) count++; // If nth such number is // found return it if (count === n) return i; } } // Driver Code document.write(findNthEvenDigitNumber(2) + "<br>" ); document.write(findNthEvenDigitNumber(10) + "<br>" ); // This code is contributed by Manoj. </script> |
Output :
2 28
Time Complexity: O(n * log10n), where n represents the given integer.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Efficient Approach
We need to find numbers made of 5 digits, 0, 2, 4, 6 and 8. When we convert a number into base 5 number, it will only be made of numbers {0, 1, 2, 3, 4}. It can be clearly seen that each digit in the required digit set {0, 2, 4, 6, 8} is double the digit in the corresponding index of the base-5 digit set. So to find the n-th number made of only even digits follow the below mentioned steps
Step 1: Convert n to n-1 this is done so as to exclude zero.
Step 2: Convert n to 5 base decimal number.
Step 3: Multiply the above found number by 2. This is the required number
C++
// Efficient C++ program to // find n-th number made of // even digits only #include<bits/stdc++.h> using namespace std; // function to find nth number // made of even digits only int findNthEvenDigitNumber( int n) { // If n=1 return 0 if (n == 1) return 0; // vector to store the digits // when converted into base 5 vector< int > v; // Reduce n to n-1 to exclude 0 n = n - 1; // Reduce n to base 5 // number and store digits while (n > 0) { // pushing the digits // into vector v.push_back(n % 5); n = n / 5; } // variable to represent the // number after converting it // to base 5. Since the digits // are be in reverse order, // we traverse vector from back int result = 0; for ( int i = v.size() - 1; i >= 0; i--) { result = result * 10; result = result + v[i]; } // return 2*result (to convert // digits 0, 1, 2, 3, 4 to // 0, 2, 4, 6, 8. return 2*result; } // Driver Code int main() { cout << findNthEvenDigitNumber(2) << endl; cout << findNthEvenDigitNumber(10) << endl; return 0; } |
Java
import java.util.*; // Efficient Java program to // find n-th number made of // even digits only class GFG { // function to find nth number // made of even digits only static int findNthEvenDigitNumber( int n) { // If n=1 return 0 if (n == 1 ) { return 0 ; } // vector to store the digits // when converted into base 5 Vector< Integer> v = new Vector<>(); // Reduce n to n-1 to exclude 0 n = n - 1 ; // Reduce n to base 5 // number and store digits while (n > 0 ) { // pushing the digits // into vector v.add(n % 5 ); n = n / 5 ; } // variable to represent the // number after converting it // to base 5. Since the digits // are be in reverse order, // we traverse vector from back int result = 0 ; for ( int i = v.size() - 1 ; i >= 0 ; i--) { result = result * 10 ; result = result + v.get(i); } // return 2*result (to convert // digits 0, 1, 2, 3, 4 to // 0, 2, 4, 6, 8. return 2 * result; } // Driver Code public static void main(String[] args) { System.out.println(findNthEvenDigitNumber( 2 )); System.out.println(findNthEvenDigitNumber( 10 )); } } // This code is contributed by PrinciRaj1992 |
Python3
# Efficient Python 3 program to find n-th # number made of even digits only # function to find nth number made of # even digits only def findNthEvenDigitNumber( n): # If n = 1 return 0 if (n = = 1 ): return 0 # vector to store the digits # when converted into base 5 v = [] # Reduce n to n-1 to exclude 0 n = n - 1 # Reduce n to base 5 number and # store digits while (n > 0 ): # pushing the digits into vector v.append(n % 5 ) n = n / / 5 # variable to represent the number # after converting it to base 5. # Since the digits are be in reverse # order, we traverse vector from back result = 0 for i in range ( len (v) - 1 , - 1 , - 1 ): result = result * 10 result = result + v[i] # return 2*result (to convert # digits 0, 1, 2, 3, 4 to # 0, 2, 4, 6, 8. return 2 * result # Driver Code if __name__ = = "__main__" : print (findNthEvenDigitNumber( 2 )) print (findNthEvenDigitNumber( 10 )) # This code is contributed by ita_c |
C#
// Efficient C# program to // find n-th number made of // even digits only using System; using System.Collections; class GFG { // function to find nth number // made of even digits only static int findNthEvenDigitNumber( int n) { // If n=1 return 0 if (n == 1) { return 0; } // vector to store the digits // when converted into base 5 ArrayList v = new ArrayList(); // Reduce n to n-1 to exclude 0 n = n - 1; // Reduce n to base 5 // number and store digits while (n > 0) { // pushing the digits // into vector v.Add(n % 5); n = n / 5; } // variable to represent the // number after converting it // to base 5. Since the digits // are be in reverse order, // we traverse vector from back int result = 0; for ( int i = v.Count - 1; i >= 0; i--) { result = result * 10; result = result + ( int )v[i]; } // return 2*result (to convert // digits 0, 1, 2, 3, 4 to // 0, 2, 4, 6, 8. return 2 * result; } // Driver Code public static void Main() { Console.WriteLine(findNthEvenDigitNumber(2)); Console.WriteLine(findNthEvenDigitNumber(10)); } } // This code is contributed by 29AjayKumar |
PHP
<?php // Efficient PHP program to find n-th // number made of even digits only // function to find nth number // made of even digits only function findNthEvenDigitNumber( $n ) { // If n=1 return 0 if ( $n == 1) return 0; // vector to store the digits // when converted into base 5 $v = array (); // Reduce n to n-1 to exclude 0 $n = $n - 1; // Reduce n to base 5 // number and store digits while ( $n > 0) { // pushing the digits // into vector array_push ( $v , $n % 5); $n = (int)( $n / 5); } // variable to represent the number // after converting it to base 5. // Since the digits are be in // reverse order, we traverse vector // from back $result = 0; for ( $i = count ( $v ) - 1; $i >= 0; $i --) { $result = $result * 10; $result = $result + $v [ $i ]; } // return 2*result (to convert // digits 0, 1, 2, 3, 4 to // 0, 2, 4, 6, 8. return 2 * $result ; } // Driver Code echo findNthEvenDigitNumber(2) . "\n" ; echo findNthEvenDigitNumber(10) . "\n" // This code is contributed by mits ?> |
Javascript
<script> // Efficient Javascript program to // find n-th number made of // even digits only // function to find nth number // made of even digits only function findNthEvenDigitNumber(n) { // If n=1 return 0 if (n == 1) { return 0; } // vector to store the digits // when converted into base 5 let v = []; // Reduce n to n-1 to exclude 0 n = n - 1; // Reduce n to base 5 // number and store digits while (n > 0) { // pushing the digits // into vector v.push(n % 5); n = Math.floor(n / 5); } // variable to represent the // number after converting it // to base 5. Since the digits // are be in reverse order, // we traverse vector from back let result = 0; for (let i = v.length - 1; i >= 0; i--) { result = result * 10; result = result + v[i]; } // return 2*result (to convert // digits 0, 1, 2, 3, 4 to // 0, 2, 4, 6, 8. return 2 * result; } // Driver Code document.write(findNthEvenDigitNumber(2)+ "<br>" ); document.write(findNthEvenDigitNumber(10)); // This code is contributed by rag2127 </script> |
Output :
2 28
Time Complexity : O(log5(n)), where n is the given integer.
Auxiliary Space: O(log5(n)), where n is the given integer.
This article is contributed by Ayush Jha.