Dado un número entero N , la tarea es encontrar el N-ésimo número puro .
Un número puro tiene que cumplir tres condiciones:
1) Tiene un número par de dígitos.
2) Todos los dígitos son 4 o 5.
3) Y el número es un palíndromo.
La serie de números puros es: 44, 55, 4444, 4554, 5445, 5555, 444444, 445544, 454454, 455554 y así sucesivamente.
Ejemplos:
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.
Enfoque: Supondremos que 2 números hacen un solo bloque. Para cada bloque, hay un número de 2 bloques de números puros. Para números puros con 1 bloque, hay 2 1 números puros; para números con 2 bloques, hay 2 2 números, y así sucesivamente.
- Los números puros que comienzan con 4, comienzan en la posición 2 del bloque : 1 , por ejemplo, 4444 está en (2 2 -1 = 3), lo que significa que está en la tercera posición de la serie.
- Los números puros que comienzan con 5 comienzan en la posición 2 bloque + 2 (bloque-1) -1 , por ejemplo, 5555 está en (2 ^ 2 + 2 ^ 1 -1 = 5), lo que significa que está en la quinta posición de la serie.
Un número puro en un bloque está esencialmente intercalado entre dos 4 o 5 y es una combinación de todos los números de bloque anteriores. Para entenderlo mejor, consideremos el siguiente ejemplo:
- El primer número puro es 44 y el segundo número puro es 55.
- 4444 (“4″+ “44” + “4”) 44 del bloque anterior
- 4554 (“4″+ “55” + “4”) 55 del bloque anterior
- 5445 (“5″+ “44” + “5”) 44 del bloque anterior
- 5555 (“5″+ “55” + “5”) 55 del bloque anterior
Este patrón se repite para todos los números de la serie.
A continuación se muestra la implementación del enfoque anterior:
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 not
bool 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) -1
bool 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 number
string 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 Code
int 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 number
import 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 not
import math
def 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) -1
def 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 number
def 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 Code
N = 5
pure = getPureNumber(N)
print(pure)
# This code is contributed by shinjanpatra
C#
// C# program to find
// the Nth pure number
using 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 not
function 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) -1
function 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 number
function 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 Code
let N = 5;
let pure = getPureNumber(N);
document.write(pure + "<br>");
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
5445
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por abhishikth aleti y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA