Dado un entero positivo N , la tarea es encontrar el número total de dígitos en la concatenación de los primeros N enteros positivos.
Ejemplos:
Entrada: N = 10
Salida: 11
Explicación:
El número formado es 12345678910.
Por lo tanto, el número total de dígitos = 11
Entrada: N = 20
Salida: 31
Explicación:
El número formado es 1234567891011121314151617181920
Por lo tanto, el número total de dígitos = 31
Planteamiento: Hagamos una observación con los ejemplos.
- Sea N = 13. Entonces, los dígitos presentes en todos los números entre 1 y 13 en el lugar de uno son 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3.
- De manera similar, los dígitos en el lugar de las decenas son 1, 1, 1, 1.
- Por lo tanto, los dígitos totales de las unidades del 1 al 13 son 13 (13 – 0).
- De manera similar, los dígitos del lugar de las decenas totales son 4 (13 – 9).
- Ahora, veamos otro número para entender el patrón. Sea N = 234. Entonces, los dígitos en el lugar de las unidades son 1 (24 veces), 2 (24 veces), 3 (24 veces), 4 (24 veces), 5 (23 veces), 6 (23 veces), 7 (23 veces), 8(23 veces), 9(23 veces), 0(23 veces). Por lo tanto, 23 * 6 + 24 * 4 = 234.
- De manera similar, los dígitos en el lugar de las decenas son 234 – 9 = 225 porque del 1 al 234, solo 1 – 9 son números de un solo dígito.
- Por último, el número de dígitos en el lugar de las centésimas es 234 – 99 = 225 del 1 al 234, solo 1 – 9 son los números de un solo dígito y 1 – 99 son los números de dos dígitos.
- Por lo tanto, el número total de dígitos formados cuando se concatenan es 234(234 – 1 + 1) + 225(234 – 10 + 1) + 135(234 – 100 + 1) = 594.
- De ahí que la idea sea restar 0, 9, 99, 999…. de N para obtener el número de dígitos en cada lugar y la suma de todo esto es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the number of // digits after concatenating the // first N positive integers #include <iostream> #include <math.h> using namespace std; // Function to find the number of // digits after concatenating the // first N positive integers void numberOfDigits(int N) { int nod = floor(log10(N) + 1); int toDecrease = (pow(10, nod) - 1) / 9; cout << (N + 1) * nod - toDecrease << endl; } // Driver code int main() { int N = 13; numberOfDigits(N); return 0; }
Java
// Java program to find the number of // digits after concatenating the // first N positive integers class GFG{ // Function to find the number of // digits after concatenating the // first N positive integers static void numberOfDigits(int N) { int nod = (int)Math.floor(Math.log10(N) + 1); int toDecrease = (int)(Math.pow(10, nod) - 1) / 9; System.out.print((N + 1) * nod - toDecrease); } // Driver code public static void main(String[] args) { int N = 13; numberOfDigits(N); } } // This code is contributed by shivanisinghss2110
Python3
# Python3 program to find the number # of digits after concatenating the # first N positive integers from math import log10, floor # Function to find the number of # digits after concatenating the # first N positive integers def numberOfDigits(N): nod = floor(log10(N) + 1); toDecrease = (pow(10, nod) - 1) // 9 print((N + 1) * nod - toDecrease) # Driver code if __name__ == '__main__': N = 13 numberOfDigits(N) # This code is contributed by mohit kumar 29
C#
// C# program to find the number of // digits after concatenating the // first N positive integers using System; class GFG{ // Function to find the number of // digits after concatenating the // first N positive integers static void numberOfDigits(int N) { int nod = (int)Math.Floor(Math.Log10(N) + 1); int toDecrease = (int)(Math.Pow(10, nod) - 1) / 9; Console.Write((N + 1) * nod - toDecrease); } // Driver code public static void Main() { int N = 13; numberOfDigits(N); } } // This code is contributed by Nidhi_Biet
Javascript
<script> // JavaScript program to implement // the above approach // Function to find the number of // digits after concatenating the // first N positive integers function numberOfDigits(N) { let nod = Math.floor(Math.log10(N) + 1); let toDecrease = (Math.pow(10, nod) - 1) / 9; document.write((N + 1) * nod - toDecrease); } // Driver code let N = 13; numberOfDigits(N); // This code is contributed by sanjoy_62. </script>
Producción:
17
Complejidad de tiempo: O(log 10 N)
Espacio auxiliar: O(1)