Count total number of digits from 1 to n
Given a number n, count the total number of digits required to write all numbers from 1 to n.
Examples:
Input : 13 Output : 17 Numbers from 1 to 13 are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13. So 1 - 9 require 9 digits and 10 - 13 require 8 digits. Hence 9 + 8 = 17 digits are required. Input : 4 Output : 4 Numbers are 1, 2, 3, 4 . Hence 4 digits are required.
Naive Recursive Method –
Naive approach to the above problem is to calculate the length of each number from 1 to n, then calculate the sum of the length of each of them. Recursive implementation of the same is –
C++
#include <bits/stdc++.h> using namespace std; int findDigits( int n) { if (n == 1) { return 1; } // Changing number to String string s = to_string(n); // Add length of number to total_sum return s.length() + findDigits(n - 1); } // Driver code int main() { int n = 13; cout << findDigits(n) << endl; return 0; } // This code is contributed by divyeshrabadiya07 |
Java
public class Main { static int findDigits( int n) { if (n == 1 ) { return 1 ; } // Changing number to String String s = String.valueOf(n); // add length of number to total_sum return s.length() + findDigits(n - 1 ); } public static void main(String[] args) { int n = 13 ; System.out.println(findDigits(n)); } } |
Python3
def findDigits(N): if N = = 1 : return 1 # Changing number to string s = str (N) # Add length of number to total_sum return len (s) + findDigits(N - 1 ) # Driver Code # Given N N = 13 # Function call print (findDigits(N)) # This code is contributed by vishu2908 |
C#
using System; using System.Collections; class GFG{ static int findDigits( int n) { if (n == 1) { return 1; } // Changing number to String string s = n.ToString(); // add length of number to total_sum return s.Length + findDigits(n - 1); } // Driver Code public static void Main( string [] args) { int n = 13; Console.Write(findDigits(n)); } } // This code is contributed by rutvik_56 |
Javascript
<script> function findDigits(n) { if (n == 1) { return 1; } // Changing number to String let s = n.toString(); // Add length of number to total_sum return (s.length + findDigits(n - 1)); } // Driver code let n = 13; document.write( findDigits(n) + "<br>" ); //This code is contributed by Mayank Tyagi </script> |
Output:
17
Time Complexity: O(n log n)
Auxiliary Space: O(n log n)
Iterative Method – (Optimized)
To calculate the number of digits, we have to calculate the total number of digits required to write at ones, tens, hundredths …. places of the number . Consider n = 13, so digits at ones place are 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3 and digits at tens place are 1, 1, 1, 1 . So, total ones place digits from 1 to 13 is basically 13 ( 13 – 0 ) and tens place digits is 4 ( 13 – 9 ) . Let’s take another example n = 234, so digits at unit place are 1 ( 24 times ), 2 ( 24 times ), 3 ( 24 times ), 4 ( 24 times ), 5 ( 23 times ), 6 ( 23 times ), 7 (23 times), 8 ( 23 times ), 9 ( 23 times ), 0 ( 23 times ) hence 23 * 6 + 24 * 4 = 234 . Digits at tens place are 234 – 9 = 225 as from 1 to 234 only 1 – 9 are single digit numbers . And lastly at hundredths place digits are 234 – 99 = 135 as only 1 – 99 are two digit numbers . Hence, total number of digits we have to write are 234 ( 234 – 1 + 1 ) + 225 ( 234 – 10 + 1 ) + 135 ( 234 – 100 + 1 ) = 594 . So, basically we have to decrease 0, 9, 99, 999 … from n to get the number of digits at ones, tens, hundredths, thousandths … places and sum them to get the required result.
Below is the implementation of this approach.
C++
// C++ program to count total number // of digits we have to write // from 1 to n #include <bits/stdc++.h> using namespace std; int totalDigits( int n) { // number_of_digits store total // digits we have to write int number_of_digits = 0; // In the loop we are decreasing // 0, 9, 99 ... from n till // ( n - i + 1 ) is greater than 0 // and sum them to number_of_digits // to get the required sum for ( int i = 1; i <= n; i *= 10) number_of_digits += (n - i + 1); return number_of_digits; } // Driver code int main() { int n = 13; cout << totalDigits(n) << endl; return 0; } |
Java
// Java program to count total number of digits // we have to write from 1 to n public class GFG { static int totalDigits( int n) { // number_of_digits store total // digits we have to write int number_of_digits = 0 ; // In the loop we are decreasing // 0, 9, 99 ... from n till // ( n - i + 1 ) is greater than 0 // and sum them to number_of_digits // to get the required sum for ( int i = 1 ; i <= n; i *= 10 ) number_of_digits += (n - i + 1 ); return number_of_digits; } // Driver Method public static void main(String[] args) { int n = 13 ; System.out.println(totalDigits(n)); } } |
Python3
# Python3 program to count total number # of digits we have to write from 1 to n def totalDigits(n): # number_of_digits store total # digits we have to write number_of_digits = 0 ; # In the loop we are decreasing # 0, 9, 99 ... from n till #( n - i + 1 ) is greater than 0 # and sum them to number_of_digits # to get the required sum for i in range ( 1 , n, 10 ): number_of_digits = (number_of_digits + (n - i + 1 )); return number_of_digits; # Driver code n = 13 ; s = totalDigits(n) + 1 ; print (s); # This code is contributed # by Shivi_Aggarwal |
C#
// C# program to count total number of // digits we have to write from 1 to n using System; public class GFG { static int totalDigits( int n) { // number_of_digits store total // digits we have to write int number_of_digits = 0; // In the loop we are decreasing // 0, 9, 99 ... from n till // ( n - i + 1 ) is greater than 0 // and sum them to number_of_digits // to get the required sum for ( int i = 1; i <= n; i *= 10) number_of_digits += (n - i + 1); return number_of_digits; } // Driver Method public static void Main() { int n = 13; Console.WriteLine(totalDigits(n)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to count // total number of digits // we have to write from // 1 to n // Function that return // total number of digits function totalDigits( $n ) { // number_of_digits store total // digits we have to write $number_of_digits = 0; // In the loop we are decreasing // 0, 9, 99 ... from n till // ( n - i + 1 ) is greater than 0 // and sum them to number_of_digits // to get the required sum for ( $i = 1; $i <= $n ; $i *= 10) $number_of_digits += ( $n - $i + 1); return $number_of_digits ; } // Driver Code $n = 13; echo totalDigits( $n ); // This code is contributed by vt_m. ?> |
Javascript
<script> // Javascript program to count total number // of digits we have to write // from 1 to n function totalDigits(n) { // number_of_digits store total // digits we have to write var number_of_digits = 0; // In the loop we are decreasing // 0, 9, 99 ... from n till // ( n - i + 1 ) is greater than 0 // and sum them to number_of_digits // to get the required sum for ( var i = 1; i <= n; i *= 10) number_of_digits += (n - i + 1); return number_of_digits; } // Driver code var n = 13; document.write(totalDigits(n)); </script> |
Output:
17
Time Complexity : O(Logn)