nu.cpp

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <math.h>

/*
	Problem: calculate the number of digits required to write all numbers in an interval [1, N] where 1 <= N <= 10^9
	Rationale: store the number of digits required to write a single number in a particular interval and size of the interval itself.
	In other words, for [1, 9], number of digits is 1 and size of the interval is 9 (i.e., we need 1 * 9 = 9 digits for this whole interval)
	For [10, 99], number of digits is 2 and size of the interval is 90 (i.e., we need 2 * 90 = 180 digits for this whole interval)
	
	Then we subtract the interval size from N until we reach a negative value (storing the total digits used so far).
*/


// Structure to store information about the number of digits and interval size
struct digits {
	int num_digits;
	long int numbers_in_interval;
};


int main()
{
	std::vector< digits > v;
	v.resize(10); // from 10^0 to 10^9

	long int n;
	long int total_digits = 0;
	int i;

	// Create vector
	for(int i = 0; i < v.size(); ++i)
	{
		v[i].num_digits = i + 1;
		v[i].numbers_in_interval = 9 * pow(10, i);
	}

	// Read input
	printf("Number: ");
	scanf("%ld", &n);
	i = 0;

	// This is where the magic happens
	while(n)
	{
		// If N is greater than the interval size, it means we'll cover the whole interval and then some more,
		// 	so we can multiply the interval size by the number of digits required to write a single number in this particular interval
		// Else, we multiply N by the number of digits required to write a single number in this interval.
		total_digits += n >= v[i].numbers_in_interval ? v[i].num_digits * v[i].numbers_in_interval : n * v[i].num_digits;
		n -= v[i].numbers_in_interval;
		++i;
	}

	printf("Digits: %ld\n", total_digits);

	return 0;
}