W miarę sensowne rozwiązanie znajduje się poniżej. Należy jednak zwrócić uwagę na to, że precyzja obliczeń zmiennoprzecinkowych może okazać się za mała dla większych wartości n (lub nawet dla odpowiednich mniejszych), oraz że nie ma żadnej weryfikacji błędów. Niemniej jednak, koncept jest bez zmian:
static size_t count_digits_log(int n)
{
size_t digits = 1 + floor(log(n)/log(10));
size_t min = pow(10, digits-1);
size_t smaller = n < 10 ? 0 : count_digits_log(min - 1);
return digits * (n - min + 1) * (n + min) / 2 + smaller;
}
char* gen_strings(int n)
{
size_t alloc_size = n + count_digits_log(n);
char* buf = (char*)malloc(alloc_size);
char* cursor = buf;
buf[0] = '\0';
for(int i = 1; i <= n; i++) {
char current[10];
int len = sprintf(current, "%d", i);
for(int j = 0; j < i; j++) {
strcat(cursor, current);
cursor += len;
}
*cursor++ = '\n';
}
cursor[-1] = '\0';
return buf;
}
https://wandbox.org/permlink/zfxZni435pJVWwAe
W przykładzie nie zwalniam pamięci.
Dodałem funkcję którą bym umieścił na produkcji (tylko skomentowałbym magiczne stałe...). Na mojej maszynie dla n=1000 funkcja z log zwraca błędne dane (czyli wychodzi niedokładność wartości zmiennoprzecinkowych):
static size_t count_digits_ifs(int n)
{
assert(n < 91055);
constexpr static auto count_in_range = [](size_t min, size_t max) {
return (max - min + 1) * (min + max) / 2;
};
if(n < 10)
return count_in_range(1, n);
if(n < 100)
return count_in_range(10, n) * 2 + 45;
if(n < 1000)
return count_in_range(100, n) * 3 + 9855;
if(n < 10000)
return count_in_range(1000, n) * 4 + 1493505;
if(n < 100000)
return count_in_range(10000, n) * 5 + 199475505;
}