Given a positive integer N, the task is to find the total number of digits in the concatenation of the first N positive integers.
Examples:
Input: N = 10
Output: 11
Explanation:
The number formed is 12345678910.
Hence, the total number of digits = 11
Input: N = 20
Output: 31
Explanation:
The number formed is 1234567891011121314151617181920
Hence, the total number of digits = 31
Approach: Lets make an observation with the examples.
- Let N = 13. So, the digits present in all the numbers between 1 to 13 at one’s place are 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3.
- Similarly, the digits at the tens place are 1, 1, 1, 1.
- So, total ones place digits from 1 to 13 are 13(13 – 0).
- Similarly, the total tens place digits are 4(13 – 9).
- Now, lets look at another number to understand the pattern. Let N = 234. So, the digits at units 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.
- Similarly, the digits at tens place are 234 – 9 = 225 because from 1 to 234, only 1 – 9 are the single-digit numbers.
- Lastly, the number of digits at the hundredths place is 234 – 99 = 225 as from 1 to 234, only 1 – 9 are the single-digit numbers and 1 – 99 are the double-digit numbers.
- Therefore, the total number of digits formed when concatenated is 234(234 – 1 + 1) + 225(234 – 10 + 1) + 135(234 – 100 + 1) = 594.
- Hence, the idea is to subtract 0, 9, 99, 999 …. from N to get the number of digits at every place and the summation of all of this is the required answer.
Below is the implementation of the above approach:
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 integersvoid numberOfDigits(int N){ int nod = floor(log10(N) + 1); int toDecrease = (pow(10, nod) - 1) / 9; cout << (N + 1) * nod - toDecrease << endl;}// Driver codeint main(){ int N = 13; numberOfDigits(N); return 0;} |
Java
// Java program to find the number of// digits after concatenating the// first N positive integersclass GFG{ // Function to find the number of// digits after concatenating the// first N positive integersstatic 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 codepublic 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 integersfrom math import log10, floor# Function to find the number of# digits after concatenating the# first N positive integersdef numberOfDigits(N): nod = floor(log10(N) + 1); toDecrease = (pow(10, nod) - 1) // 9 print((N + 1) * nod - toDecrease)# Driver codeif __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 integersusing System;class GFG{ // Function to find the number of// digits after concatenating the// first N positive integersstatic 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 codepublic 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 integersfunction 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> |
Output:
17
Time Complexity: O(log10N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
