Primero considere el problema ” Dado un número n, encuentre S (n) , los números debajo de n tienen el mismo primer y último dígito “. Su problema puede resolverse usando esto (para su rango [A, B], la respuesta será S [B] -S [A-1].
Ahora encontrando S [N] : Sea L el número de dígitos en N.
Es fácil encontrar números de longitud < L que tengan el mismo primer y último dígito (para un primer y último dígito fijo, todos los del medio son posibles. Entonces [matemática] 9 \ veces 10 ^ {L-2} [/ matemática].
- ¿Cómo los logaritmos convierten la multiplicación en suma?
- ¿Cuáles son los problemas en informática para los cuales se conoce con certeza la mejor complejidad computacional absoluta?
- ¿Cuáles son algunos conceptos en el cálculo lambda que es bueno saber antes de aprender programación funcional?
- Int a [6] = {1,2,4,5,}; ¿Es correcta esta afirmación en el concepto de matrices?
- ¿Cómo publicaría una observación matemática que he probado en una computadora?
Para números de longitud L y primer dígito menores que el primer dígito de N , nuevamente son posibles todos los del medio.
Para números de longitud L y primer dígito iguales al primer dígito de N , tenemos que encontrar cuántos dígitos L-2 medios son posibles. Considere el número M que tiene todos los dígitos iguales a N, excepto que el último dígito es igual al primer dígito. Por ejemplo, N = 3101, entonces M = 3103, si N = 3106 entonces M = 3103.
Si M <= N , entonces todos los dígitos medios menores o iguales a los dígitos medios de M son posibles.
De lo contrario, M> N , luego reste 1 del penúltimo dígito de M para obtener M ‘ , y todos los dígitos medios de M’ serán posibles. Tenga en cuenta que esta resta puede necesitar llevar, por ejemplo, para N = 3101, M = 3103 y M ‘ = 3093, dando 9 posibles valores medios.
Agregue los valores en los tres casos anteriores para obtener la respuesta.
Complejidad: Todos los pasos anteriores necesitaban [matemática] O (L) [/ matemática] pasos. Entonces, para la consulta [matemática] [A, B] [/ matemática], complejidad si [matemática] O (log (B)) [/ matemática].
