structures interview data book and algorithms aho algorithm data-structures

algorithm - interview - Encuentra el kth once-no-número libre



data structures and algorithms pdf (8)

Editar: Este enfoque pierde el once-no número 1011 libre por ejemplo. Sé lo que está mal y lo arreglaré, pero no puedo hacerlo ahora.

Tomemos un enfoque basado en principios que desarrolle la solución en lugar de tratar de manejarlo todo de una vez.

Deje que S sea la secuencia de potencias de 11:

11, 121, 1331, 14641, 161051, ...

Sea E (n) el conjunto de números que contiene la representación de cadena de n como una subcadena. El conjunto que está buscando es la unión de E (n) sobre n en S.

¿Cómo generamos los elementos de E (n) para algunos n? (Tomemos n = 121 por ejemplo)

Haz un gráfico acíclico dirigido donde n es el nodo raíz. Haz n apunta a los 19 de los siguientes números:

Agregar 0-9: n0 n1 n2 n3 n4 n5 n6 n7 n8 n9
Prefijo 1-9: 1n 2n 3n 4n 5n 6n 7n 8n 9n

Repita el proceso para cada uno de estos nuevos nodos. Observe que ciertos nodos pueden terminar con más de un padre, por lo que querrá mantener un hashmap de número a puntero de nodo. (Puede obtener 71217 por 121 -> 1217 -> 71217 o 121 -> 7121 -> 71217.)

Este gráfico tiene la propiedad de que, para cualquier borde de u a v, tenemos u <v. Esto es importante porque significa que podemos generar los elementos de E (n) en orden creciente haciendo una generación de ancho del primer gráfico , siempre expandiendo el nodo no expandido con el número más pequeño.

Ahora combine estos gráficos para todos los n en S.

Tiene un gran gráfico acíclico dirigido (que es infinito) que puede generar de forma amplia, siempre expandiendo el nodo no expandido con el número más pequeño, emitiendo el siguiente (kth) número once no libre.

Pseudocódigo

Funciona, lo probé. Aquí hay una esencia de C #: https://gist.github.com/timothy-shields/8026924

procedure generate_eleven_non_free i = 1 n = 11^i //frontier nodes; F.insert(x) does nothing if x already in F F = empty-min-heap-set while (true) { if (F.empty() or F.min() > n) { F.insert(n) i = i + 1 n = 11^i } else { m = F.extractmin() yield m for j = 0:9 F.insert(append(m,j)) for j = 1:9 F.insert(append(j,m)) } }

Para obtener el número kth once-non-free, simplemente haz algo como generate_eleven_non_free (). Element_at (k), donde se supone que debe seleccionar el número kth yield.

Vamos a definir eleven-non-free números eleven-non-free :

Si consideramos un número como una cadena, entonces si alguna subcadena interna es una potencia (distinta de cero) de 11 , entonces este número es un número eleven-non-free .

Por ejemplo, 1123 es un número eleven-non-free ya que 11 dentro es 11^1 . También 12154 es uno como 121 es 11^2 . Pero 12345 no lo es, porque no podemos encontrar ninguna potencia de 11 distinta de cero en el interior.

Entonces, si le das ak, encuentra el número kth eleven-non-free . Por ejemplo, el decimotercer número es 211 .

No sé cómo hacerlo eficientemente. la forma de fuerza bruta es aumentar i de 1 y verificar cada número y contar hasta la k.

Supongo que deberíamos considerar cadenas con diferente longitud (1, 2, 3, 4, ...). luego, para cada longitud, tratamos de completar 11, 11 ^ 2, 11 ^ 3, etc. y tratamos de obtener todas las combinaciones.

Pero parece bastante complicado también.

¿Nadie?

Como buen punto de partida es considerar el problema relacionado de contar cuántos números enteros de once no libres (ENF) hay de N dígitos. Esto no es exactamente lo mismo que encontrar el enésimo entero ENF, pero este último problema se puede reducir al anterior bastante fácilmente (ver el final de esta publicación para el código Java que hace esto).

La idea es hacer programación dinámica en prefijos. Para cualquier cadena de dígitos s , y cualquier entero k , deje que N(k,s) denote el número de cadenas ENF de longitud k que comienzan con s . Y, para cualquier cadena s , s_0 sea ​​el sufijo más largo de s que también aparece como un prefijo de cualquier potencia de once (POE) de longitud k o menos. Entonces, suponiendo que s no contiene ninguna subcadena POE, tenemos la ecuación:

N(k,s) = N(k-length(s)+length(s_0),s_0)

El razonamiento detrás de esta ecuación es el siguiente. Como s_0 es un sufijo de s , escribamos s como una concatenación de alguna otra cadena q s_0 : s=[q,s_0] . Ahora, seamos r cualquier cadena de dígitos que empiece por s y nuevamente escribiremos esto como una concatenación, como r=[s,r_0] = [q,s_0,r_0] .

Si r contiene un POE como una subcadena, entonces este POE está contenido en r_0 , o cruza el límite entre s y r_0 . En este caso, s debe terminar en un prefijo POE, y, dado que sabemos que el prefijo POE más largo que ocurre como un sufijo de s es s_0 , se sigue que si r contiene una subcadena POE, entonces esta subcadena debe estar contenida en [s_0,r_0] . Esto nos da una correspondencia uno a uno entre los ENF que comienzan con s=[q,s_0] y los ENF que comienzan con s_0 .

Esta ecuación anterior da lugar a un algoritmo recursivo para contar el número de ENF de dígitos k con un prefijo dado. Los casos base terminan siendo instancias donde length(s_0)=length(s) que significa que s sí mismo es un prefijo de un POE de longitud k o menos. Como no hay muchos prefijos POE tales (a lo sumo k elije 2 que es O (k ^ 2)), esta fórmula conduce a un algoritmo eficiente. Aquí está el pseudocódigo:

Given a prefix s and an integer k, this function computes N(k,s) if s contains a POE then return 10^(k-length(s)) if length(s) = k return 0 let s0 = longest POE prefix which is a suffix of s if(length(s0)<length(s)) return N(k-length(s)+length(s0),s0) total = 0 for d = "0" to "9" total += N(k,concatenate(s,d)) return total

Usando la programación dinámica, el tiempo de ejecución de este algoritmo será polinomial en k, el número de dígitos. El algoritmo solo recurre en los prefijos POE, y dado que hay O (k ^ 2) de estos, el tiempo de ejecución será O (k ^ 2) multiplicado por el tiempo de ejecución de cada iteración. El uso de un algoritmo ingenuo O (k ^ 2) para encontrar el sufijo más largo que coincida con un prefijo POE conduciría a un algoritmo O (k ^ 4), mientras que usar un árbol raíz para encontrar coincidencias en tiempo lineal resultaría en O (k ^ 3). El código java dado a continuación usa el algoritmo ingenuo, y experimentalmente, para valores de hasta k = 100 parece ser Θ (k ^ 4.5), aunque esta discrepancia podría deberse a detalles de implementación o factores constantes que afectan los tiempos de ejecución para tamaños de entrada pequeños. . Aquí está el código:

public class Eleven { public static final String[] digits = {"0","1","2","3","4","5","6","7","8","9"}; public static BigInteger countENF(String prefix, int k){ return countENF(prefix,k,new HashMap(),getPowers(k)); } public static BigInteger countENF(String prefix, int k, // This map contains stored results for dynamic programming // Pair is an auxiliary class that does what you think it does Map<Pair<String,Integer>,BigInteger> resultMap, // precomputed list of powers of 11 List<String> powers ){ // Dynamic programming case BigInteger res = resultMap.get(new Pair(prefix,k)); if(res != null) return res; // base cases if(!isEFree(prefix, powers)){ res = new BigInteger("10").pow(k-prefix.length()); resultMap.put(new Pair<>(prefix,k), res); return res; } if(prefix.length() >= k){ res = new BigInteger("0"); resultMap.put(new Pair<>(prefix,k), res); return res; } String s0 = getMaxPrefix(prefix, powers); if(s0.length() < prefix.length()){ return countENF(s0,k+s0.length()-prefix.length(),resultMap,powers); } // recursive summation res = new BigInteger("0"); for(String d : digits){ String s1 = prefix + d; res = res.add(countENF(s1,k,resultMap,powers)); } resultMap.put(new Pair<>(prefix, k), res); return res; } // // helper functions // // returns all POEs of at most length digits private static List<String> getPowers(int length) { List<String> ret = new ArrayList<>(); BigInteger val = new BigInteger("11"); BigInteger eleven = new BigInteger("11"); while(val.toString().length() <= length){ ret.add(val.toString()); val = val.multiply(eleven); } return ret; } // finds the longest string that is both a prefix of s and a suffix of a POE private static String getMaxSuffix(String s, List<String> powers){ for(int i=s.length(); i>0; i--){ String sub = s.substring(0,i); for(String p : powers){ if(p.endsWith(sub)) return sub; } } return ""; } public static boolean isEFree(String s, List<String> powers){ for(String p : powers){ if(s.indexOf(p)>=0) return false; } return true; }

Como se mencionó anteriormente, este algoritmo no resuelve el problema exacto en el OP. Pero modificar este código para encontrar realmente el n''th número ENF es bastante simple. Realizando llamadas repetidas a countENF , primero calculamos cuántos dígitos tiene el n''th número ENF, y luego, un dígito a la vez, calculamos los dígitos del n''th ENF de izquierda a derecha.

public static String getNthENF(BigInteger i){ int k = i.toString().length(); HashMap results = new HashMap(); List<String> powers = getPowers(k); while(countENF("",k,results,powers).compareTo(i) < 0){ k++; powers = getPowers(k); } String solution = ""; BigInteger total = new BigInteger("0"); while(solution.length() < k){ for(String d : digits){ BigInteger newTotal = total.add(countENF(solution + d,k,results,powers)); int comp = newTotal.compareTo(i); if(comp >= 0){ solution = solution + d; break; } total = newTotal; } } return solution; }

Aquí hay un ejemplo de salida, que da N''th ENF como se computa utilizando programación dinámica, así como el uso de fuerza bruta, para potencias de 10.

Dynamic Programming: 10^1: 118 10^2: 1178 10^3: 11680 10^4: 115730 10^5: 1146628 10^6: 11360558 10^7: 112558960 10^8: 1115229050 10^9: 11049731548 10^10: 103258311161 10^11: 935443232311 10^12: 8576360477119 10^13: 79330786951511 10^14: 732117130575070 10^15: 6880811638385388 10^16: 64284911460844887 10^17: 610616803411054857 10^18: 5759459802926457113 10^19: 54555977711878792498 10^20: 518773721711219891634 Brute Force: 10^1: 118 10^2: 1178 10^3: 11680 10^4: 115730 10^5: 1146628 10^6: 11360558 10^7: 112558960

Es interesante la facilidad con la que la gente se asusta con el término "fuerza bruta" sin siquiera intentar cuantificarlo :)

La solución de fuerza bruta es en realidad O (R * log R)

donde R es el resultado ( k -undécimo-número no libre). Simplemente pruebe todos los números 1..R y para cada uno de ellos realice búsquedas de cadenas para 11, 121, 1331, 14641, etc. utilizando el autómata preparado (para la cantidad de dígitos dada). O(R * log R) no se ve tan mal , si lo miras de esta manera, ¿verdad? :-)

¿Solución de generación?

La idea inteligente es tratar de generar el número más directamente:

  1. generando directamente el k -ésimo número;
  2. o generando secuencialmente todos los números 1- k once-no libres;
  3. o al generar los once números no libres <10 ^ n a la vez y ordenarlos.

La solución 1 debería ser muy inteligente, si no casi imposible. La solución 2 parece mejor que la solución de fuerza bruta porque omite esos números que no son once, no libres. La solución 3 sería una alternativa fácil de implementar, lo que nos lleva a una importante cuestión:

¿Cuántos once números no libres <10 n existen?

Fácil combinatoria (funciona exactamente para n <= 10; para una n más alta, es una aproximación cercana, descuidando que 11 2 es una subcadena de 11 13 y 11 es una subcadena de 11 11 y 11 19 ):

¡tan básico para el límite 10 n usted obtiene más de 10 soluciones n-2 ! Esto significa que la cantidad de soluciones es una proporción constante del límite, lo que significa que

O (R) = O (k)

lo que implica que

¡La solución de fuerza bruta es en realidad O (k * log k), así como la solución de generar todo !

La temida solución de fuerza bruta parece mucho mejor ahora, ¿no? Sin embargo, sigue siendo el mismo :)

¿Podemos mejorar esto?

  • Solución 1: sería una posibilidad, pero cercana a la magia.
  • Solución 2: lo mejor que puedes esperar es O(k) pero deberías ser muy cuidadoso para lograr esto. Habrá muchas complicaciones que harán que resulte incómodo seleccionar el próximo once más pequeño, no de número libre. Por ejemplo, al generar todos los 11xxx, 121xx, 1331x, p. Ej. 13121 está en el medio, dificultando cualquier generación automática de números ordenados , y menos duplicidades causadas por patrones que aparecen en dígitos xxx. Probablemente terminará con una estructura de datos complicada que forzará O(log k) en cada paso, y por lo tanto O(k log k) en total.
  • Solución 3: esto que ya sabemos es O(k log k) , que es lo mismo que encontrar el número k -ésimo.

Esto me suena como un algoritmo de divide y vencerás.

Este problema se siente muy similar a: http://www.geeksforgeeks.org/divide-and-conquer-maximum-sum-subarray/

y esto: http://en.wikipedia.org/wiki/Maximum_subarray_problem

Cuando divides, divide los Strings originales en 2 partes que son aproximadamente 1/2 de grande. En la parte inferior de su recursión, usted tiene problemas fáciles con cadenas pequeñas de 1 char que son todas once libres (porque no contienen suficientes caracteres para tener poderes de 11 dentro).

El "truco" entra cuando "intensificas" en la recursión. En este paso, debe aprovechar el hecho de que cualquier "potencia" (es decir, 121) que busca DEBE puentear el "medio" de la cadena de entrada.

Por ejemplo, cuando "avanzas" desde Cadenas de longitud 1 a Cadenas de longitud 2, sabrás que parte de la potencia que estás buscando está en la primera mitad, y parte está en la segunda mitad de la cadena de entrada .

Esto se ve como un O(klog^2(k)) :

def add(vals, new_vals, m, val): if val < m and val not in vals and val not in new_vals: new_vals.append(val) def kth11(k): vals = [ 11**i for i in range(1, k+1) ] new_vals = [ ] while True: vals = sorted(vals + new_vals) vals = vals[:k] m = vals[-1] new_vals = [ ] for v in vals: for s in range(1, 10): val = int(str(s) + str(v)) add(vals, new_vals, m, val) for s in range(0, 10): val = int(str(v) + str(s)) add(vals, new_vals, m, val) if len(new_vals) == 0: break return vals[-1] print kth11(130)

OK, esto tomó varios días para averiguarlo. Lo primero que hay que entender es que el único requisito concreto del rompecabezas euler 442 del que se deriva esta pregunta es resolver E (10 ^ 18). Los ejemplos no relacionados de lo que significa un número libre de 11 son solo distracciones.

La opción de fuerza bruta está fuera de discusión, por dos razones.

  1. Requiere literalmente una comparación de cuerdas quintilianas y tomaría una semana para resolverse en la mayoría de las computadoras hogareñas.

  2. Leonhard Euler era matemático, por lo que el espíritu de la pregunta debe interpretarse en ese contexto.

Después de un tiempo, comencé a centrarme en la coincidencia de patrones para potencias de 10, en lugar de incluir continuamente poderes de 11 en mis algoritmos. Después de calcular cuáles son los poderes de 11, terminaste con todo lo relacionado con eso. Solo representan cadenas. Ni siquiera están incluidos en el algoritmo final, solo se usan en el trabajo detectivesco.

Empecé tratando de obtener una comprensión detallada de cómo se introducen nuevos números que contienen 11 entre potencias de 10 y si había un patrón predecible. Si lo hubo, entonces solo sería una cuestión de usar ese patrón para deducir todos los 11 números que contienen introducidos antes de cualquier 10 ^ punto de detención.

Comprender los conceptos principales

Por cada nuevo 10 ^ alcanzado, el número de coincidencias anteriores de 11 ^ string es idéntico al rango 10 ^ anterior. Es más fácil de explicar con un gráfico.

Aquí hay una lista de 10 ^ 2 - 10 ^ 6 que muestra el recuento de los nuevos números que contienen 11 introducidos hasta ahora y agrupados por el número 11 ^ que coincide con la cadena.

Fig. 1.) Número de 11 ^ coincidencias en 10 ^ rangos agrupados por 11 ^ coincidencia de cadena

--------------------------- 10^2 range (10 - 100) --------------------------- 11 1 --------------------------- 10^3 range (100 - 1000) --------------------------- 11 18 121 1 --------------------------- 10^4 range (1000 - 10000) --------------------------- 11 260 121 18 1331 1 --------------------------- 10^5 range (10000 - 100000) --------------------------- 11 3392 121 260 1331 18 14641 1 --------------------------- 10^6 range (100000 - 1000000) --------------------------- 11 41760 121 3392 1331 260 14641 18 161051 1 etc...

Hay dos requisitos para hacer esta lista.

  1. Cuando se combinan secuencialmente varios números que contienen 11 (como 11000 - 11999), todos esos elementos deben atribuirse al grupo 11 ^ de la primera coincidencia. Lo que significa que, aunque haya coincidencias para 121 y 1331 en ese ejemplo, todas las coincidencias en ese rango se atribuyen a 11, porque es lo primero.

  2. Los emparejamientos se realizan en base a la posibilidad más corta primero. es decir, 11, 121, 1331, etc. Esto se debe a que algunos números coinciden con múltiples 11 ^ strings mientras que otros aparecen dentro de un rango contiguo. Y, igualarlos de mayor a menor, no produce un patrón predecible. Funcionalmente, es todo lo mismo. Esto solo trae mucha claridad a la imagen.

Observe que en cada rango nuevo de 10 ^, solo se introduce 1 nuevo 11 ^ partido. Y, el número de coincidencias para cada número anterior de 11 ^ es idéntico, independientemente de la potencia anterior. La dificultad aquí es que el número de coincidencias de cadena * 11 no puede inferirse directamente de la potencia anterior.

Fig. 2.) Diferenciando otros 11 ^ patrones del partido * 11

****11 ***110 pattern **1100 pattern *11000 pattern 110000 pattern etc...

Todas las coincidencias de "patrón" son altamente predecibles dentro de 10 ^ potencias. Solo los números * 11 no son obvios en la forma en que se acumulan. En realidad, no es que no haya un patrón, el problema es que tendrías que presumir números que fueron escaneados de derecha a izquierda y, como resultado, ninguno si los otros patrones ya serían predecibles.

Como resultado, se debe rastrear un acumulador por separado al mismo tiempo que nos permite usar las * 11 coincidencias anteriores para calcular el número de nuevas * 11 coincidencias. Para cualquiera de ustedes genios matemáticos, puede haber una solución más elegante. Pero, aquí está el mío.

Siempre debe realizar un seguimiento por separado de la cantidad de * 11 coincidencias de las 2 potencias anteriores . Usando estos como operandos, puede calcular la cantidad de * 11 coincidencias para la potencia actual.

Ejemplo:

El número de * 11 coincidencias en el rango 10 ^ 3 es 8. También hay 10 coincidencias en "110" pero no importan aquí, solo estamos rastreando números que terminan con "11". Por lo tanto, estamos comenzando con los 2 recuentos de partidos previos * 11 que son 8 y 0 de los 2 rangos 10 ^ anteriores .

Importante: para cualquier número menor que 10 ^ 2, 0 es el recuento de coincidencia anterior para este cálculo. Es por eso que 0 es el segundo operando de búsqueda hacia atrás cuando se trabaja con 10 ^ 3.

Fig. 3.) Cómo calcular * 11 recuentos de partidos por 10 ^ rango utilizando seguimiento

10^3 | 80 = 8 * 10 - 0; 10^4 | 792 = 80 * 10 - 8; 10^5 | 7840 = 792 * 10 - 80;

Sin embargo, este número solo es útil al mirarlo, nuevamente, desde una perspectiva diferente.

Fig 4.) Ilustración de cómo escalan los grupos por potencias de 10

================================== # Formulas for 10^4 ================================== 80 **11 = 8 * 10 - 0 80 *110 pattern = previous power''s *11 times 10 100 1100 pattern = previous power''s 110 times 10 ================================== 260 Total matches in range ================================== # Formulas for 10^5 ================================== 792 ***11 = 80 * 10 - 8 800 **110 pattern = previous power''s **11 times 10 800 *1100 pattern = previous power''s *110 times 10 1000 11000 pattern = previous power''s 1100 times 10 ================================== 3392 Total matches in range

En estos ejemplos, solo el número * 11 debe calcularse por separado. Ver estos números apilados como este tipo de hace que se sienta más complicado de lo que es. Solo es importante entender el concepto. En la práctica, abstraemos todo menos el cálculo * 11 a través de la multiplicación acumulativa.

Ahora, antes de entrar en un algoritmo de trabajo, lo último que se debe entender conceptualmente es cómo usar estos patrones para calcular el número Nth 11 que termina en cada ^ 10.

Este es un proceso de dos pasos, así que lo demostraré usando un ejemplo. Veamos el rango 1000 - 10000 de la figura 1. 10000 es 10 ^ 4, así que ese es el rango para el que estamos resolviendo.

Los siguientes 11 ^ grupos están todos dentro de ese rango. El 18 y el 1 pueden derivarse de las potencias anteriores (ver Fig 1).

match # --------------- 11 260 121 18 1331 1

  1. Calcule el total de 11 coincidencias en el rango actual de 10 ^ 4. Para hacer esto, primero tenemos que calcular el valor para la categoría de coincidencia "11". El valor 260 anterior se puede calcular utilizando números de los rangos anteriores y los operandos de seguimiento * 11 por separado, como sigue:

    Calculando * 11 cuentas por 10 ^ 4

    260 = (18 * 10) + (8 * 10 - 0)

    • Donde 18 es el total de todas las "11" coincidencias (no necesariamente * 11) del rango 10 ^ 3 (ver Fig 1).
    • Los 10 son constantes.
    • Y, 8 y 0 son nuestros puntos de partida, mencionados anteriormente, para calcular por separado * 11 cambios.

  2. Combina el resultado de 10 ^ 4 con todos los demás resultados hasta 10 ^ 2. Nota: El total de coincidencias para 10 ^ 2 es 1 porque solo hay un número que contiene 11 desde 0 hasta 100.

    Total 11-containing numbers in 10^4 range: 279 = 260 + 18 + 1 Total 10^4 range plus previous totals : 299 = 279 + 19 + 1 --------------------- 10^4 solved: 9701 = 10^4 - 299

Un algoritmo de trabajo

Aquí hay un algoritmo escrito en C # que resuelve para cada uno de 10 ^ 1 a 10 ^ 18. Vuelve casi al instante. Por respeto al euler del proyecto, no publiqué la respuesta a su rompecabezas directamente. La salida es precisa sin embargo. En este momento, la pregunta n. ° 442 solo muestra que 163 personas han resuelto el problema en comparación con 336260 personas que resolvieron el problema n. ° 1. Si ese número comienza a crecer sin ningún motivo, eliminaré esta publicación.

private ulong GetNthElevenFreeForPow10(uint pow){ if(pow > 18) throw new ArgumentException("Argument must be a positive integer between 1 and 18", "pow"); // All of the numbers up to 10^0 & 10^1 are 11-free // if 1 is considered 11-free as the euler question // states. if (pow == 0 || pow == 1) return (ulong)Math.Pow(10, pow); // The sequence of 11s doesn''t form a repeatable pattern // until 10^4 because it requires back tracking to // calculated running totals. if (pow == 2) return (ulong)Math.Pow(10, pow) - 1; if (pow == 3) return (ulong)Math.Pow(10, pow) - (18 + 1 + 1); // At each new power the number of elevens created is // easily predicted based on the previous power. But, // the number of new entries ending with 11 i.e.) xxx11 // is a little trickier. It requires a lookback at the // two previous powers. This array stores the lookback // operands used to make that calculation. ulong[] lookbackOperands = new ulong[] { 0, 8 }; // this number is used to calculate all of the new 11-containing // numbers for each power. The next power is always a calculation // on the previous. ulong elevensConsumedCurrent = 18; ulong elevensConsumedPrevious = 18 + 1; // this number holds a running total all 11-containing // numbers consumed so far. ulong elevensConsumedTotal = 20; for (int n = 4; n <= pow; n++) { // Calculate the number of new items added that end with "11". ulong endsWith11Current = lookbackOperands[1] * 10 - lookbackOperands[0]; lookbackOperands[0] = lookbackOperands[1]; lookbackOperands[1] = endsWith11Current; elevensConsumedCurrent = elevensConsumedCurrent * 10 + endsWith11Current; elevensConsumedPrevious += elevensConsumedCurrent; elevensConsumedTotal += elevensConsumedPrevious; } return (ulong)Math.Pow(10, pow) - elevensConsumedTotal; }

Uso:

StringBuilder sb = new StringBuilder(); for (uint n = 1; n <= 18; n++) sb.AppendLine(String.Format( "Nth 11-Free Number @ 10^{0}/t{1}", n, GetNthElevenFreeForPow10(n).ToString() ) ); Console.WriteLine(sb.ToString());

Aquí están los primeros 15.

Nth 11-Free Number @ 10^1 10 Nth 11-Free Number @ 10^2 99 Nth 11-Free Number @ 10^3 980 Nth 11-Free Number @ 10^4 9701 Nth 11-Free Number @ 10^5 96030 Nth 11-Free Number @ 10^6 950599 Nth 11-Free Number @ 10^7 9409960 Nth 11-Free Number @ 10^8 93149001 Nth 11-Free Number @ 10^9 922080050 Nth 11-Free Number @ 10^10 9127651499 Nth 11-Free Number @ 10^11 90354434940 Nth 11-Free Number @ 10^12 894416697901 Nth 11-Free Number @ 10^13 8853812544070 Nth 11-Free Number @ 10^14 87643708742799 Nth 11-Free Number @ 10^15 867583274883920

10^18 es realmente, muy grande. La fuerza bruta no es tu amiga.

Sin embargo, observemos algunas conveniencias:

  • Si una cadena s representa un número once no libre, entonces trivialmente también lo hace ds (donde d es una cadena de dígitos).
  • Si quisiera saber cuántos números de k dígitos son once, no libres, podría basar eso en cuántos números de k-1 dígitos son once, no libres.
  • (por ejemplo, ¿cuántos números 1xx son once no libres? Bueno, ¿cuántos números xx son once no libres? Obviamente, al menos, muchos números 1xx son once no libres ... Los únicos casos adicionales son cuando un poder de once comienza con el dígito al comienzo, con el 1 que acaba de clavar en el frente).
  • Esto sugiere un enfoque de programación dinámica relativamente directo para descubrir cuántos números once no libres están en una cadena de longitud conocida con un prefijo fijo. (por ejemplo, cuántos once números no libres están en 934xxxxx)

Finalmente, arroje un poco de lógica de estilo de búsqueda binaria en la parte superior, y debería poder encontrar exactamente qué número es el número N-ésimo-no-libre.

given ak, find the kth eleven-non-free number. ... es una gran pregunta.

Como esto es cuestión de tiempo, estoy escribiendo un pseudo código.

  1. Primer paso Mantenga los poderes de once a mano

var eleven_powers = []; for (var i=0; i<1000; i++) eleven_powers.push(Math.pow(11,i));

  1. Segundo paso Mantenga todos non-eleven-free números posibles que non-eleven-free en la medida de lo posible. Esto tendrá que tratar con enteros grandes.

for (var i=11; i<Integer.MAX_VALUE; i++){ if(string(i).substring(for each of eleven_powers) == true) store it sequentially results_array }

  1. Tercer paso Take k, return results_array[k]