Finding n-th number made of prime digits (2, 3, 5 and 7) only
Given a number βnβ, find the nth number whose each digit is a prime number i.e 2, 3, 5, 7. . . In other words, find the nth number of this sequence. 2, 3, 5, 5, 22, 23β¦β¦
Given that the nth number such found will be less than equal to 10^18
Examples :
Input: 10
Output: 3
Explanation: 2, 3, 5, 7, 22, 23, 25, 27, 32, 33Input: 21
Output: 222
Finding the n-th number made of prime digits (2, 3, 5, and 7) using Mathematics:
There are four prime digits 2, 3, 5, and 7. The first observation is that the number of numbers of x length and made of prime digits are 4x because for each position you have 4 choices so the total number is 4^x. So the total count of such numbers whose length is = 1 to len (i.e. 2 or 3 or more) will be 4*((4len β 1)/3). (This is the sum of G.P with first term 4 and common ratio 4)
Follow the steps below to solve the problem:
- First finds the number of digits in the n-th number using the above observation. Start from len = 0 and keep incrementing it while the value of it is smaller than 4*((4len β 1)/3).
- Now we know the number of digits in the n-th number. We also know the count of numbers with (len-1) digits. Let this count be prev_count. Now one by one find digits in our result.
- First, fix 2 at the ith place (assuming all the places up to i-1 are already filled), we have 4(len β i) numbers possible and to check if 2 is the right candidate or not check if the count of numbers after putting 2 is greater than or equal to n or not. If it is true then 2 is the right candidate if this is not true this means if we fix 2 at the ith place only prev_count + 4(len-i) numbers can be covered.
- So increase prev_count by 4(len-i) and repeat this step for 3 checks if 3 fits at ith place or not. If not go for 5. If 5 also does not fit, go for 7. It is guaranteed that 7 will fit it if 2, 3, and 5 do not fit because we are sure that the length of the nth such number is len only.
Below is the implementation of the above steps:
C++
// C++ implementation for finding nth number // made of prime digits only #include <bits/stdc++.h> using namespace std; // Prints n-th number where each digit is a // prime number void nthprimedigitsnumber( long long n) { // Finding the length of n-th number long long len = 1; // Count of numbers with len-1 digits long long prev_count = 0; while ( true ) { // Count of numbers with i digits long long curr_count = prev_count + pow (4, len); // if i is the length of such number // then n<4*(4^(i-1)-1)/3 and n>= 4*(4 ^ i-1)/3 // if a valid i is found break the loop if (prev_count < n && curr_count >= n) break ; // check for i + 1 len++; prev_count = curr_count; } // Till now we have covered 'prev_count' numbers // Finding ith digit at ith place for ( int i = 1; i <= len; i++) { // j = 1 means 2 j = 2 means ...j = 4 means 7 for ( long long j = 1; j <= 4; j++) { // if prev_count + 4 ^ (len-i) is less // than n, increase prev_count by 4^(x-i) if (prev_count + pow (4, len - i) < n) prev_count += pow (4, len - i); // else print the ith digit and break else { if (j == 1) cout << "2" ; else if (j == 2) cout << "3" ; else if (j == 3) cout << "5" ; else if (j == 4) cout << "7" ; break ; } } } cout << endl; } // Driver function int main() { nthprimedigitsnumber(10); nthprimedigitsnumber(21); return 0; } |
Java
// Java implementation for finding nth number // made of prime digits only import static java.lang.Math.pow; class Test { // Prints n-th number where each digit is a // prime number static void nthprimedigitsnumber( long n) { // Finding the length of n-th number long len = 1 ; // Count of numbers with len-1 digits long prev_count = 0 ; while ( true ) { // Count of numbers with i digits long curr_count = ( long )(prev_count + pow( 4 , len)); // if i is the length of such number // then n<4*(4^(i-1)-1)/3 and n>= 4*(4 ^ i-1)/3 // if a valid i is found break the loop if (prev_count < n && curr_count >= n) break ; // check for i + 1 len++; prev_count = curr_count; } // Till now we have covered 'prev_count' numbers // Finding ith digit at ith place for ( int i = 1 ; i <= len; i++) { // j = 1 means 2 j = 2 means ...j = 4 means 7 for ( long j = 1 ; j <= 4 ; j++) { // if prev_count + 4 ^ (len-i) is less // than n, increase prev_count by 4^(x-i) if (prev_count + pow( 4 , len - i) < n) prev_count += pow( 4 , len - i); // else print the ith digit and break else { if (j == 1 ) System.out.print( "2" ); else if (j == 2 ) System.out.print( "3" ); else if (j == 3 ) System.out.print( "5" ); else if (j == 4 ) System.out.print( "7" ); break ; } } } System.out.println(); } // Driver method public static void main(String args[]) { nthprimedigitsnumber( 10 ); nthprimedigitsnumber( 21 ); } } |
Python3
# Python3 implementation for # finding nth number made of # prime digits only import math # Prints n-th number where # each digit is a prime number def nthprimedigitsnumber(n): # Finding the length # of n-th number len = 1 ; # Count of numbers # with len-1 digits prev_count = 0 ; while ( 1 ): # Count of numbers # with i digits curr_count = (prev_count + math. pow ( 4 , len )); # if i is the length of such # number then n<4*(4^(i-1)-1)/3 # and n>= 4*(4 ^ i-1)/3 if a valid # i is found break the loop if (prev_count < n and curr_count > = n): break ; # check for i + 1 len + = 1 ; prev_count = curr_count; # Till now we have covered # 'prev_count' numbers # Finding ith digit at ith place for i in range ( 1 , len + 1 ): # j = 1 means 2 j = 2 # means ...j = 4 means 7 for j in range ( 1 , 5 ): # if prev_count + 4 ^ (len-i) # is less than n, increase # prev_count by 4^(x-i) if (prev_count + pow ( 4 , len - i) < n): prev_count + = pow ( 4 , len - i); # else print the ith # digit and break else : if (j = = 1 ): print ( "2" , end = ""); elif (j = = 2 ): print ( "3" , end = ""); elif (j = = 3 ): print ( "5" , end = ""); elif (j = = 4 ): print ( "7" , end = ""); break ; print (); # Driver Code nthprimedigitsnumber( 10 ); nthprimedigitsnumber( 21 ); # This code is contributed by mits |
C#
// C# implementation for finding nth // number made of prime digits only using System; public class GFG { // Prints n-th number where each // digit is a prime number static void nthprimedigitsnumber( long n) { // Finding the length of n-th number long len = 1; // Count of numbers with len-1 digits long prev_count = 0; while ( true ) { // Count of numbers with i digits long curr_count = ( long )(prev_count + Math.Pow(4, len)); // if i is the length of such number // then n<4*(4^(i-1)-1)/3 and n>= 4*(4 ^ i-1)/3 // if a valid i is found break the loop if (prev_count < n && curr_count >= n) break ; // check for i + 1 len++; prev_count = curr_count; } // Till now we have covered 'prev_count' numbers // Finding ith digit at ith place for ( int i = 1; i <= len; i++) { // j = 1 means 2 j = 2 means ...j = 4 means 7 for ( long j = 1; j <= 4; j++) { // if prev_count + 4 ^ (len-i) is less // than n, increase prev_count by 4^(x-i) if (prev_count + Math.Pow(4, len - i) < n) prev_count += ( long )Math.Pow(4, len - i); // else print the ith digit and break else { if (j == 1) Console.Write( "2" ); else if (j == 2) Console.Write( "3" ); else if (j == 3) Console.Write( "5" ); else if (j == 4) Console.Write( "7" ); break ; } } } Console.WriteLine(); } // Driver method public static void Main() { nthprimedigitsnumber(10); nthprimedigitsnumber(21); } } // This code is contributed by Sam007 |
PHP
<?php // PHP implementation for finding // nth number made of prime digits only // Prints n-th number where // each digit is a prime number function nthprimedigitsnumber( $n ) { // Finding the length // of n-th number $len = 1; // Count of numbers // with len-1 digits $prev_count = 0; while (true) { // Count of numbers // with i digits $curr_count = $prev_count + pow(4, $len ); // if i is the length of such // number then n<4*(4^(i-1)-1)/3 // and n>= 4*(4 ^ i-1)/3 if a valid // i is found break the loop if ( $prev_count < $n && $curr_count >= $n ) break ; // check for i + 1 $len ++; $prev_count = $curr_count ; } // Till now we have covered // 'prev_count' numbers // Finding ith digit at ith place for ( $i = 1; $i <= $len ; $i ++) { // j = 1 means 2 j = 2 // means ...j = 4 means 7 for ( $j = 1; $j <= 4; $j ++) { // if prev_count + 4 ^ (len-i) // is less than n, increase // prev_count by 4^(x-i) if ( $prev_count + pow(4, $len - $i ) < $n ) $prev_count += pow(4, $len - $i ); // else print the ith // digit and break else { if ( $j == 1) echo "2" ; else if ( $j == 2) echo "3" ; else if ( $j == 3) echo "5" ; else if ( $j == 4) echo "7" ; break ; } } } echo "\n" ; } // Driver Code nthprimedigitsnumber(10); nthprimedigitsnumber(21); // This code is contributed by ajit ?> |
Javascript
<script> // javascript implementation for finding nth number // made of prime digits only // Prints n-th number where each digit is a // prime number function nthprimedigitsnumber(n) { // Finding the length of n-th number var len = 1; // Count of numbers with len-1 digits var prev_count = 0; while ( true ) { // Count of numbers with i digits var curr_count = (prev_count + Math.pow(4, len)); // if i is the length of such number // then n<4*(4^(i-1)-1)/3 and n>= 4*(4 ^ i-1)/3 // if a valid i is found break the loop if (prev_count < n && curr_count >= n) break ; // check for i + 1 len++; prev_count = curr_count; } // Till now we have covered 'prev_count' numbers // Finding ith digit at ith place for ( var i = 1; i <= len; i++) { // j = 1 means 2 j = 2 means ...j = 4 means 7 for ( var j = 1; j <= 4; j++) { // if prev_count + 4 ^ (len-i) is less // than n, increase prev_count by 4^(x-i) if (prev_count + Math.pow(4, len - i) < n) prev_count += Math.pow(4, len - i); // else print the ith digit and break else { if (j == 1) document.write( "2" ); else if (j == 2) document.write( "3" ); else if (j == 3) document.write( "5" ); else if (j == 4) document.write( "7" ); break ; } } } document.write( '<br>' ); } // Driver method nthprimedigitsnumber(10); nthprimedigitsnumber(21); // This code is contributed by Amit Katiyar </script> |
33 222
Time Complexity: O(Constant), Length of digits in the worst case will be 18, to count numbers with len β 1 will take 18 operations and to calculate the nth it will take 18 * 4 = 72, so total operation will be 90 which is constant.
Auxiliary Space: O(1)
Approach 2:
The idea to make the nth number by identifying the below pattern:
/ | | \
2 3 5 7
/ | | \ / | | \ / | | \ / | | \
22 23 25 27 32 33 35 37 52 53 55 57 72 73 75 77
/||\/||\/||\/||\ /||\/||\/||\/||\ /||\/||\/||\/||\ /||\/||\/||\/||\
We can notice following :
1st. 5th, 9th. 13th, β¦.. numbers have 2 as last digit.
2nd. 6th, 10th. 14th, β¦.. numbers have 3 as last digit.
3rd. 7th, 11th. 15th, β¦.. numbers have 5 as last digit.
4th. 8th, 12th. 16th, β¦.. numbers have 7 as last digit.
Follow the steps below to solve the problem:
- First, calculate the remainder when the n is divided by 4 to identify which number is there at that place.
- After identifying the number add that number to the answer.
- At last reduce the nth number by dividing it by 4 to calculate the rest of the numbers.
- Repeat above steps till n becomes zero.
Below is the implementation of above approach:
C++
// CPP program to find n-th number with // prime digits 2, 3, 5 and 7 #include <algorithm> #include <iostream> #include <string> using namespace std; string nthprimedigitsnumber( int number) { int rem; string num; while (number) { // remainder for check element position rem = number % 4; switch (rem) { // if number is 1st position in tree case 1: num.push_back( '2' ); break ; // if number is 2nd position in tree case 2: num.push_back( '3' ); break ; // if number is 3rd position in tree case 3: num.push_back( '5' ); break ; // if number is 4th position in tree case 0: num.push_back( '7' ); break ; } if (number % 4 == 0) number--; number = number / 4; } reverse(num.begin(), num.end()); return num; } // Driver code int main() { int number = 21; cout << nthprimedigitsnumber(10) << "\n" ; cout << nthprimedigitsnumber(21) << "\n" ; return 0; } |
Java
// Java program to find n-th number with // prime digits 2, 3, 5 and 7 import java.util.*; class GFG{ static String nthprimedigitsnumber( int number) { int rem; String num= "" ; while (number> 0 ) { // remainder for check element position rem = number % 4 ; switch (rem) { // if number is 1st position in tree case 1 : num+= '2' ; break ; // if number is 2nd position in tree case 2 : num+= '3' ; break ; // if number is 3rd position in tree case 3 : num+= '5' ; break ; // if number is 4th position in tree case 0 : num+= '7' ; break ; } if (number % 4 == 0 ) number--; number = number / 4 ; } return new StringBuilder(num).reverse().toString(); } // Driver code public static void main(String[] args) { int number = 21 ; System.out.println(nthprimedigitsnumber( 10 )); System.out.println(nthprimedigitsnumber( 21 )); } } // This code is contributed by mits |
Python3
# Python3 program to find n-th number # with prime digits 2, 3, 5 and 7 def nthprimedigitsnumber(number): num = ""; while (number > 0 ): # remainder for check element position rem = number % 4 ; # if number is 1st position in tree if (rem = = 1 ): num + = '2' ; # if number is 2nd position in tree if (rem = = 2 ): num + = '3' ; # if number is 3rd position in tree if (rem = = 3 ): num + = '5' ; # if number is 4th position in tree if (rem = = 0 ): num + = '7' ; if (number % 4 = = 0 ): number = number - 1 number = number / / 4 ; return num[:: - 1 ]; # Driver code number = 21 ; print (nthprimedigitsnumber( 10 )); print (nthprimedigitsnumber(number)); # This code is contributed by mits |
C#
// C# program to find n-th number with // prime digits 2, 3, 5 and 7 using System; class GFG{ static string nthprimedigitsnumber( int number) { int rem; string num= "" ; while (number>0) { // remainder for check element position rem = number % 4; switch (rem) { // if number is 1st position in tree case 1: num+= '2' ; break ; // if number is 2nd position in tree case 2: num+= '3' ; break ; // if number is 3rd position in tree case 3: num+= '5' ; break ; // if number is 4th position in tree case 0: num+= '7' ; break ; } if (number % 4 == 0) number--; number = number / 4; } char [] st = num.ToCharArray(); Array.Reverse(st); return new string (st); } // Driver code static void Main() { int number = 21; Console.WriteLine(nthprimedigitsnumber(10)); Console.WriteLine(nthprimedigitsnumber(number)); } } // This code is contributed by mits |
PHP
<?php // PHP program to find n-th number with // prime digits 2, 3, 5 and 7 function nthprimedigitsnumber( $number ) { $num = "" ; while ( $number > 0) { // remainder for check element position $rem = $number % 4; switch ( $rem ) { // if number is 1st position in tree case 1: $num .= '2' ; break ; // if number is 2nd position in tree case 2: $num .= '3' ; break ; // if number is 3rd position in tree case 3: $num .= '5' ; break ; // if number is 4th position in tree case 0: $num .= '7' ; break ; } if ( $number % 4 == 0) $number --; $number = (int)( $number / 4); } return strrev ( $num ); } // Driver code $number = 21; print (nthprimedigitsnumber(10) . "\n" ); print (nthprimedigitsnumber( $number )); // This code is contributed by mits |
Javascript
<script> // Javascript program to find n-th number with prime digits 2, 3, 5 and 7 function nthprimedigitsnumber(number) { let rem; let num= "" ; while (number>0) { // remainder for check element position rem = number % 4; switch (rem) { // if number is 1st position in tree case 1: num+= '2' ; break ; // if number is 2nd position in tree case 2: num+= '3' ; break ; // if number is 3rd position in tree case 3: num+= '5' ; break ; // if number is 4th position in tree case 0: num+= '7' ; break ; } if (number % 4 == 0) number--; number = parseInt(number / 4, 10); } let st = num.split( '' ); st.reverse(); return (st.join( "" )); } let number = 21; document.write(nthprimedigitsnumber(10) + "</br>" ); document.write(nthprimedigitsnumber(number)); </script> |
33 222
Time Complexity: O(log4(N)), Looping till the Nth number becomes zero which is reducing by 4 every time.
Auxiliary Space: O(1)