Find the Nth Pure number
Given an integer N, the task is to find the Nth pure number.
A pure number has to satisfy three conditions:
1) It has an even number of digits.
2) All digits are either 4 or 5.
3) And the number is a palindrome.
The Pure number series is: 44, 55, 4444, 4554, 5445, 5555, 444444, 445544, 454454, 455554 and so on.
Examples:
Input: 5 Output: 5445 Explanation: 5445 is the 5th pure number in the series. Input: 19 Output: 45444454 Explanation: 45444454 is the 19th pure number in the series.
Approach: We will assume that 2 numbers make one single block. For each block, there is a 2block number of pure numbers. For pure numbers with 1 block, there are 21 pure numbers; for numbers with 2 blocks, there are 22 numbers, and so on.
- Pure numbers starting with 4, start at position 2block – 1 for example, 4444 is at (22 -1 = 3) which means it is, at third position in the series.
- Pure numbers starting with 5 starts at position 2block + 2(block-1) -1 for example, 5555 is at (2^2 + 2^1 -1 =5) which means it is at the fifth position in the series.
A pure number in a block is essentially sandwiched between two 4’s or 5’s and is a combination of all previous block numbers. To understand it better, let’s consider the example below:
- The first pure number is 44 and the second pure number is 55.
- 4444 (“4″+ “44” + “4”) 44 from previous block
- 4554 (“4″+ “55” + “4”) 55 from previous block
- 5445 (“5″+ “44” + “5”) 44 from previous block
- 5555 (“5″+ “55” + “5”) 55 from previous block
This pattern repeats for all the numbers in the series.
Below is the implementation of the above approach:
C++
#include<bits/stdc++.h>using namespace std;// CPP program to find// the Nth pure num// Function to check if it// is a power of 2 or notbool isPowerOfTwo(int N){ double number = log(N)/log(2); int checker = int(number); return number - checker == 0;}// if a number belongs to 4 series// it should lie between 2^blocks -1 to// 2^blocks + 2^(blocks-1) -1bool isSeriesFour(int N, int digits){ int upperBound = int(pow(2, digits)+pow(2, digits - 1)-1); int lowerBound = int(pow(2, digits)-1); return (N >= lowerBound) && (N < upperBound);}// Method to find pure numberstring getPureNumber(int N){ string numbers[N + 1]; numbers[0] = ""; int blocks = 0; int displacement = 0; // Iterate from 1 to N for (int i = 1; i < N + 1; i++) { // Check if number is power of two if (isPowerOfTwo(i + 1)) { blocks = blocks + 1; } if (isSeriesFour(i, blocks)) { displacement = int(pow(2, blocks - 1)); // Distance to previous // block numbers numbers[i] = "4" + numbers[i - displacement] + "4"; } else { displacement = int(pow(2, blocks)); // Distance to previous // block numbers numbers[i] = "5" + numbers[i - displacement] + "5"; } } return numbers[N];}// Driver Codeint main(){ int N = 5; string pure = getPureNumber(N); cout << pure << endl;}// This code is contributed by Surendra_Gangwar |
Java
// Java program to find// the Nth pure numberimport java.io.*;class PureNumbers { // Function to check if it // is a power of 2 or not public boolean isPowerOfTwo(int N) { double number = Math.log(N) / Math.log(2); int checker = (int)number; return number - checker == 0; } // if a number belongs to 4 series // it should lie between 2^blocks -1 to // 2^blocks + 2^(blocks-1) -1 public boolean isSeriesFour( int N, int digits) { int upperBound = (int)(Math.pow(2, digits) + Math.pow(2, digits - 1) - 1); int lowerBound = (int)(Math.pow(2, digits) - 1); return (N >= lowerBound) && (N < upperBound); } // Method to find pure number public String getPureNumber(int N) { String[] numbers = new String[N + 1]; numbers[0] = ""; int blocks = 0; int displacement = 0; // Iterate from 1 to N for (int i = 1; i < N + 1; i++) { // Check if number is power of two if (isPowerOfTwo(i + 1)) { blocks = blocks + 1; } if (isSeriesFour(i, blocks)) { displacement = (int)Math.pow( 2, blocks - 1); // Distance to previous // block numbers numbers[i] = "4" + numbers[i - displacement] + "4"; } else { displacement = (int)Math.pow( 2, blocks); // Distance to previous // block numbers numbers[i] = "5" + numbers[i - displacement] + "5"; } } return numbers[N]; } // Driver Code public static void main(String[] args) throws Exception { int N = 5; // Create an object of the class PureNumbers ob = new PureNumbers(); // Function call to find the // Nth pure number String pure = ob.getPureNumber(N); System.out.println(pure); }} |
Python3
# Python program to find# the Nth pure num# Function to check if it# is a power of 2 or notimport mathdef isPowerOfTwo(N): number = math.log(N)/math.log(2) checker = math.floor(number) return number - checker == 0# if a number belongs to 4 series# it should lie between 2^blocks -1 to# 2^blocks + 2^(blocks-1) -1def isSeriesFour(N, digits): upperBound = math.floor(math.pow(2, digits) + math.pow(2, digits - 1)-1) lowerBound = math.floor(math.pow(2, digits)-1) return (N >= lowerBound) and (N < upperBound)# Method to find pure numberdef getPureNumber(N): numbers = ["" for i in range(N + 1)] numbers[0] = "" blocks = 0 displacement = 0 # Iterate from 1 to N for i in range(1,N + 1): # Check if number is power of two if (isPowerOfTwo(i + 1)): blocks = blocks + 1 if (isSeriesFour(i, blocks)): displacement = math.floor(math.pow(2, blocks - 1)) # Distance to previous # block numbers numbers[i] = f"4{numbers[i - displacement]}4" else: displacement = math.floor(math.pow(2, blocks)) # Distance to previous # block numbers numbers[i] = f"5{numbers[i - displacement]}5" return numbers[N]# Driver CodeN = 5pure = getPureNumber(N)print(pure)# This code is contributed by shinjanpatra |
C#
// C# program to find// the Nth pure numberusing System; class PureNumbers { // Function to check if it // is a power of 2 or not public bool isPowerOfTwo(int N) { double number = Math.Log(N) / Math.Log(2); int checker = (int)number; return number - checker == 0; } // if a number belongs to 4 series // it should lie between 2^blocks -1 to // 2^blocks + 2^(blocks-1) -1 public bool isSeriesFour( int N, int digits) { int upperBound = (int)(Math.Pow(2, digits) + Math.Pow(2, digits - 1) - 1); int lowerBound = (int)(Math.Pow(2, digits) - 1); return (N >= lowerBound) && (N < upperBound); } // Method to find pure number public string getPureNumber(int N) { string[] numbers = new string[N + 1]; numbers[0] = ""; int blocks = 0; int displacement = 0; // Iterate from 1 to N for (int i = 1; i < N + 1; i++) { // Check if number is power of two if (isPowerOfTwo(i + 1)) { blocks = blocks + 1; } if (isSeriesFour(i, blocks)) { displacement = (int)Math.Pow( 2, blocks - 1); // Distance to previous // block numbers numbers[i] = "4" + numbers[i - displacement] + "4"; } else { displacement = (int)Math.Pow( 2, blocks); // Distance to previous // block numbers numbers[i] = "5" + numbers[i - displacement] + "5"; } } return numbers[N]; } // Driver Code public static void Main() { int N = 5; // Create an object of the class PureNumbers ob = new PureNumbers(); // Function call to find the // Nth pure number string pure = ob.getPureNumber(N); Console.Write(pure); }}// This code is contributed by chitranayal |
Javascript
<script>// Javascript program to find// the Nth pure num// Function to check if it// is a power of 2 or notfunction isPowerOfTwo(N){ let number = Math.log(N)/Math.log(2); let checker = Math.floor(number); return number - checker == 0;}// if a number belongs to 4 series// it should lie between 2^blocks -1 to// 2^blocks + 2^(blocks-1) -1function isSeriesFour(N, digits){ let upperBound = Math.floor(Math.pow(2, digits) + Math.pow(2, digits - 1)-1); let lowerBound = Math.floor(Math.pow(2, digits)-1); return (N >= lowerBound) && (N < upperBound);}// Method to find pure numberfunction getPureNumber(N){ let numbers = new Array(N + 1); numbers[0] = ""; let blocks = 0; let displacement = 0; // Iterate from 1 to N for (let i = 1; i < N + 1; i++) { // Check if number is power of two if (isPowerOfTwo(i + 1)) { blocks = blocks + 1; } if (isSeriesFour(i, blocks)) { displacement = Math.floor(Math.pow(2, blocks - 1)); // Distance to previous // block numbers numbers[i] = "4" + numbers[i - displacement] + "4"; } else { displacement = Math.floor(Math.pow(2, blocks)); // Distance to previous // block numbers numbers[i] = "5" + numbers[i - displacement] + "5"; } } return numbers[N];}// Driver Codelet N = 5;let pure = getPureNumber(N);document.write(pure + "<br>");// This code is contributed by _saurabh_jaiswal</script> |
Output:
5445
Time Complexity: O(NlogN) as using pow function in a loop
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
