Algorithm for counting digits

[Elijah]

I've my own but it seems too simple and inefficient. We have this exercise problem to create a C program for counting the number of digits in each number.

example, number 10 has 11 digits - (1-9 has 9 digits all together and lastly 10 has 2, so 11 digits overall).

Now my algorithm would be to check the number while incrementing it until it reaches zero.

for(count=0;digit>0;++count)
if(digit<10)
digit=digit-1;
if(digit>9)
digit=digit-2;
if(digit>99)
digit=digit-3;
...
if(digit>999999999)
digit=digit-9;


Now my program would be bulky with all that if statements, so inefficient. I can't think of a better algorithm than this, anyone had some ideas for this?

Thanks for your time :)

[Palin]

is you store the digit as a string you could just use strlen :) would be quicker.

[Elijah]

I don't know the syntax of strlen, last I tried I got a segmentation fault, any other way for this? loops? arrays?

[Palin]

strlen(char *) will return an int or long I cant remeber you will need to include string.h for you to use this.


#include <iostream.h>
#include <string.h>

int main(){
char *digit = "1101";
int length = 0;

cout <<"number:" <<digit <<" length:" <<strlen(digit) <<endl;
return strlen(digit);
}



ofcourse this could be made more complicated but with out knowing what exactly you are doing I can't.

[Elijah]

Originally posted by Palin
strlen(char *) will return an int or long I cant remeber you will need to include string.h for you to use this.


#include <iostream.h>
#include <string.h>

int main(){
char *digit = "1101";
int length = 0;

cout <<"number:" <<digit <<" length:" <<strlen(digit) <<endl;
return strlen(digit);
}



ofcourse this could be made more complicated but with out knowing what exactly you are doing I can't.
Thanks very much Palin :) I think I can use that one, my syntax must be wrong though.

[sensei@kendo]

Maybe I missunderstood the whole problem, but if you put "10" in a string and use strlen it will return 2 instead of the needed result 11.

My suggestion:

int getdigits(long number)
{
int digits = 0;
int tocount;
long div=1;
for(int power=1;div>0;power++)
{
div=number/pow(10,power);
tocount=number%pow(10,power);
tocount-=tocount%pow(10,power-1);
digits+=power*(tocount+1); //0 is a digit as well, if you don't want to count it decrement the result by 1
}
return digits;
}

[Elijah]

Originally posted by sensei@kendo
Maybe I missunderstood the whole problem, but if you put "10" in a string and use strlen it will return 2 instead of the needed result 11.

My suggestion:

int getdigits(long number)
{
int digits = 0;
int tocount;
long div=1;
for(int power=1;div>0;power++)
{
div=number/pow(10,power);
tocount=number%pow(10,power);
tocount-=tocount%pow(10,power-1);
digits+=power*(tocount+1); //0 is a digit as well, if you don't want to count it decrement the result by 1
}
return digits;
}
hmmm, you're right :eek: my program isn't working right no wonder, strlen cannot be used on this problem since it will return the length of the digits itself rather than the numbers that I'm looking for. Thanks for pointing that out :) I'm currently studying your program right now ... I think I almost got it. Hmmm, maybe I could just use the same algorithm and do a 'for' loop similar to yours.

[sensei@kendo]

replace
tocount-=tocount%pow(10,power-1); with:
if(power>=2)
tocount/=pow(10,power-1);

and

digits+=power*(tocount+1);
with:
digits+=(tocount+1);

I would stay away from your algorithm since it seems a little slow to me....you can replace all the if's with a little mathematical power ;)

My algorithm basically works with division, modulo and the power of 10.

It starts with 10 by the power of 1.

Divide the whole number to find out if there's a second digit: if you divide 10 by 10^1 it will result in 1. So the loop goes on.

Then get the modulo of the division. for example if you have 19 '%' 10^1 (the c-character for modulo) it will result 9.

The next line is for numbers bigger than 99. For example: you have the number 123, in the second run of the loop power will be 2 so you have following results out of the three calculations:
123/10^2=1
123%10^2=23
23/10^1=2

which gives you the right number for the second digit: 2



Question: If you have a second digit bigger than 1, for example 2, do you need to count like 0, 1, 2 or 10, 11, 12, 13,....20?

[bwkaz]

What's your definition of "digit"?

My definition says that 10 has 2 digits. 100 has 3, and 1000 has 4. 9 has 1. By my definition of "digit", strlen would work wonderfully.

Apparently your definition differs?

[Elijah]

no, actually that's exactly what I mean here bwkaz (e.g. 132=3digits, 1000=4digits etc. ), but I'm not sure about the strlen, I think I'll just use the simple tools for this one.

I'm still working on the problem though <brain overload> hehe, sorry my C is kinda crappy.

here's some sample inputs and outputs:
input:
11
13
59
60
output:
10
11
34
Impossible!


60 cannot be used since there's a remainder in there ...
<still working on it> <needs coffee>

[sensei@kendo]

Ok then I really missunderstood the whole problem....The whole 10 has 11 digits thing confused me....strlen would work, if you don't want to use it for any reason try this:

int getdigits(long number)
{
long div=1;
int power=0;
do{
power++;
div=number/pow(10,power);
}while(div>0);
return power;
}

[Elijah]

here's my old code:
#include<stdio.h>
void countreturn(long digit);

int main(void)
{
long digi=0;
scanf("%d", &digi);
countreturn(digi);
return 0;
}

void countreturn(long digit)
{
int i=0, j=0, count=0, var[10], err=0;
for(i=0; i<=10; i++)
{
var[i] = i+1;
}

for(count=0; digit>0; ++count)
{
if(digit < 10)
j = 0;
if(digit > 9)
j = 1;
if(digit > 99)
j = 2;
if(digit > 999)
j = 3;
if(digit > 9999)
j = 4;
if(digit > 99999)
j = 5;
if(digit > 999999)
j = 6;
if(digit > 9999999)
j = 7;
if(digit > 99999999)
j = 8;
if(digit > 999999999)
j = 9;
if(digit >= 2000000000)
{
printf("Impossible! \n");
break;
err=1;
}
if(digit > 9999999999)
j = 10;
if((digit-9) % var[j] !=0)
{
printf("Impossible!\n");
err=1;
break;
}
digit = digit - var[j];
}
if(err==0)
printf("%d\n", count);
}


of course this code is pretty lame, with some errors too ...
here's my recent one:
#include<stdio.h>
void countreturn(long digit);

int main(void)
{
long digi=0;
scanf("%d", &digi);
countreturn(digi);
return 0;
}

void countreturn(long digit)
{
long i, k=1, j=0, var[10], lgthvar[10], count = 0;
for(i=0; i<10; i++)
{
var[i] = i+1;
printf("variable=%d\n", var[i]);
}
for(i=0; i<10; i++)
{
lgthvar[i] = k*10;
k = lgthvar[i];
printf("length=%d\n", lgthvar[i]);
}

for(count=0; digit>0; count++)
{
for(i=0; i<10; i++)
{
if(digit<10)
j = var[0];
else
if(digit>lgthvar[i])
j = var[i];
}
digit = digit - j;
}
printf("%d\n", count);
}
shorter, but it's not working! :o

[Hena]

I havent coded with c++ (little c), but...
long count_digits(long value) {
long a=1;
double extra;
while (extra>1) {
extra=value/10
a++;
}
return a;
}
You need to check that a though. It might need to start from 0. I always make mistakes with that +/-1 :).

[goon12]

This should tell you the number of digits entered:

#include<stdio.h>

#define BUF_SIZE 256
int main()
{
char *num;
int i;
int c = 0;

memset(num, 0, sizeof(num));
printf("Enter some digits: ");
fgets(num, BUF_SIZE, stdin);


for( i = 0; i <= strlen(num); i++ )
{
if( isdigit(num[i]) >= 1 )
{
c++;
}
}

printf("Number of digits: %d\n", c);

return 0;
}



-goon12

[Strike]

Python troll:


num = raw_input ("Your number: ")
print len(num)


:D

[Palin]

welp thats what i get for looking at programming problems after midnight. Sorry about that

actually I read the whole thread I know I could use a clerification of what you mean by digit.

[Elijah]

sorry if it isn't quite clear, here's the quote from the problem, it's actually one of the questions being asked on the last acm programming contest (last years), this'll probably be a breeze to some of you cause it's the second problem, the rest are too hard but quite a challenge:

Book Pages:
How many digits would you need to use to number the pages of a 10 page book? Pages 1 to 9 would require 1 digit each (total 9), and page 10 would require 2 digits. This makes 11 digits. Similarly, a book of 34 pages would require 59 digits.

Can we work backwards? If you are told that a book requires 13 digits to number its pages, can you work out how many pages the book has? I hope so, because that is all you have to do for this problem. Each line in the input file represents the number of digits used in numbering a book. Your answer will be the number of pages the book has. If the number supplied cannot possibly be valid, your answer should be "impossible!" Beware that Acmonian books can be quite large, and the number of digits required for a given Acmonian book can reach 2,000,000,000.

Here's what I've done so far, it's buggy - it mysteriously never exits the first while loop, doesn't output the correct answer for numbers higher than one billion. where: 1999999998 should output: 234567900. And like my other programs, it's sloooow :(

#include<stdio.h>
void countreturn(long digit);

FILE *inputpages;

int main(void)
{
long digi=0;
inputpages = fopen("inputpages.txt", "r");
while((digi=getc(inputpages)) != EOF)
{
ungetc(digi,inputpages);
fscanf(inputpages,"%d", &digi);
countreturn(digi);
}
return 0;
}

void countreturn(long digit)
{
long i, k=1, j=0, var[10], lgthvar[10], count = 0;
for(i=0; i<10; i++)
{
var[i] = i+1;
}
for(i=0; i<10; i++)
{
lgthvar[i] = k*10;
k = lgthvar[i];
}

for(count=0; digit>0; ++count)
{
for(i=0; i<10; i++)
{
if(digit<10)
{
j=1;
break;
}
if(digit>lgthvar[i])
{
j=var[i+1];
break;
}
if((digit-9)%var[j]!=0 || digit > 2000000000)
{
printf("Impossible!\n");
return;
}
}
digit = digit - j;
}
printf("%d\n", count);
}


For the others who posted some helpful codes, Thanks but I still don't understand how dividing the digit by 10^x would get me anywhere :confused:.
Could be great if it can be used I figure that could speed things up, but .. how?

[Elijah]

oh, for the inputpages.txt it should have these:
11
13
59
60
1999999998
#

should output this:
10
11
34
Impossible!
234567900


for my inputpages.txt file I only included the rest except 199999998, cause of course, it takes too long :D my algorithm's bad. And if it did get me the results for the huge number, it's still wrong.
I haven't programmed in awhile, wow this is quite fun :p

[Hena]

Once more into the breach ... Meaning one more try, now that think i understand the problem :). Reminding to test that and also "#include <math.h>" is needed.
long count_digits (long given) {
long i,value=given,ret=0;
while (value>=10) {
value=value/10;
i++;
}
for (;i>=0;i--) {
given=given-9*i);
if (given>0) {
ret+=given*pow(10,i);
value=given;
} else {
ret+=given;
}
}
return ret;
}

Edit: Damn, nice typing fix :p.

[Elijah]

Originally posted by Hena
Once more into the breach ... Meaning one more try, now that think i understand the problem :). Reminding to test that and also "#include <math.h>" is needed.
long count_digits (long given) {
long i,value=given,ret=0;
while (value>=10) {
value=value/10;
i++;
}
for (;i>=0;i--) {
given=given-9*i);
if (given>0) {
ret+=given*pow(10,i);
value=given;
} else {
ret+=given;
}
}
return ret;
}

Edit: Damn, nice typing fix :p.
tried following the process by paper, I used 11 as the given and it returned 20 :confused: (supposed to be 10), hmm I'll try it again ... I might be wrong though .

[Hena]

Damn, yeah it wrong. Gimme a few secs to refigure it out :D.

[Hena]

Right. Change
if (given>0) {
ret+=given*pow(10,i);
value=given;
}
to
if (given>0) {
ret+=given*(i+1);
value=given;
}

Edit: same typing error... huoh :)

[sensei@kendo]

this should work, I tested it out a little...

long getcount(long digits)
{

if(digits<=9)
return digits;
long pages=9;
digits-=9;
int times_subtractable=1;
int stop;
for(int power=2;digits>0;power++)
{
stop=0;

while(!stop)
{
if((10*power)<digits)
{
digits-=(10*power);
pages+=10;
times_subtractable++;
if(digits==0||times_subtractable==10)
stop=1;
}
else
{
if(digits%power!=0)
return -1;
pages+=(digits/power);
digits=0;
stop=1;
}
}
times_subtractable=0;
}
return pages;
}

[Elijah]

I used a series of comparisons in this prob, number by number (increments until it lasts) so it's very slow. It'll compare and keep adding counts if there is a match. <- my algorithm.

But I noticed most used 10^ in the problem and either dividing or subtracting it, I still can't figure it out yet. Would anyone explain this to me? I think this could be the one that's missing in my program, sorry, I'm not an quite the math expert and I've lots to learn :)

[truls]

The REALLY sneaky solution:
int num = 20;
char buf[10];
int len = 0;
while(num>0) {
len += strlen(itoa(num,buf,10));
num--;
}
cout << "Number of digits: " << len << endl;


Somewhat more efficient:
int num = 25;
int len = 0;
while(num>0) {
int digits = num;
while( digits>0 ) {
digits = digits/10;
len++;
}
num--;
}
cout << "Number of digits: " << len << endl;

The point is that the number of digits in a number equals the number of times you can divide this number by 10 plus one.

100/10 = 10;
10/10 = 1;
1/10 = 0;

100 can be divided by 10 two times. Two + one = three.
The number of digits in 100 is three.

[bwkaz]

If you just want to find out the number of digits in a number (rather than all that hassle with converting it to a string), you can take the logarithm base 10.

Which is what the log10() function in math.h uses. ;)

So something like this would work -- I'm not sure on speed, but it would work:

#include <math.h>

int numdigits(int n)
{
if(n == 0) return 0;

return (int)(floor(log10(n))+1);
}

int main()
{
// Finds the number of your definition of "digits" in NUMBER:
const int NUMBER=10;
int counter=0;
int i;

for(i=1; i<=NUMBER; i++) {
counter += numdigits(i);
}

printf("The number of \"digits\" in %d is %d.\n", NUMBER, counter);

return 0;
} Compile with gcc -o test test.c -lm if you want to make sure it works the way you want it to. I think it does. 10 gives 11, 100 gives 192, 11 gives 13, and 234567900 gives that huge number that they had (19999....8 or whatever it was). Unfortunately, on numbers as big as 234567900, it takes a full minute to run. :-/

I'm sure there's a way to do it in log(n) time, but I can't figure that way out....

[bwkaz]

Here we go, here's a better (read: quicker) way to do it.

First, notice that if you clamp the number (call it i) down to some multiple of 10, it becomes easy to count what you call digits. There are 9 1-digit numbers (that are counted), 90 2-digit numbers, and 900 3-digit numbers. Etc., etc.

So, you figure out how "big" the number you're going up to is. For example, 3000 would get a value of 1000 for this, since 1000 is the largest power of 10 less than 3000.

Then, we can easily figure out the sum up to that "big"ness value. When the value is 1000, the "sum" is 1*9 + 2*90 + 3*900. It's the sum of (9*i)*10^(i-1), for values of i from 1 to log-base-10 of "big"ness.

So calculate that sum, that's what I'm doing here in the for loop. Set the counter to that value.

Then, you still have (for example) 1000 up through 3000 to count. All of these numbers have the same number of digits, 4, and you can do a bit of simple math (3000 - 1000 + 1) to figure out how many there are. Multiply this by the number of digits in them, and add that to the counter.

Then, counter is the value you wanted.

We don't even need to use log10()! :)

int main()
{
// Finds the number of your definition of "digits" in NUMBER:
const int NUMBER=101;
int counter=0;
int i = NUMBER;
int j, k;
int bigness = 1;

// get bigness to be the "bigness" value of i, the largest power
// of 10 that's <= i.

while(bigness <= NUMBER/10)
bigness *= 10;

// There are 9 single-digit numbers, 90 double-digit ones,
// etc., etc. So multiply the number of numbers by the
// number of digits in each, and add that to counter.
//
// k is the number of digits in each

for(j=1,k=1; j<bigness; j*=10,k++) {
counter += (9 * j) * k;
}

// counter includes all the numbers up to bigness-1, no more.

// Subtracting off (bigness-1) will take away all the numbers
// that we've already counted.

i -= (bigness-1);

// And what's left in i is the number of numbers left to count.
// k is the number of digits in each of them, because it's the
// number of digits in bigness (and in i).

counter += i * k;

printf("The number of \"digits\" in %d is %d.\n", NUMBER, counter);

return 0;
} If there's any part of the math that doesn't make any sense, I can try to explain it.

[elderdays]

He needs an algorithm:

A digit in the one's place is multiplied by 1,
A digit in the ten's place is multiplied by 10,
A digit in the hundred's place is multiplied by 100,
etc...
Then those products are added together and that is the value needed.

Strenlength or whatever it was (I don't know C++) would tell you how many products you would be adding together in the end.

Is there nothing that will return the value of a specific character in a string? Something like charat(2) to return the value of the second character in a string. You could use that with strenlength (string length) and say, OK, character at position x * 1, + character at position y * 10, + character at position z * 100, etc...

Maybe that would work. I am wanting to learn C++ but don't have time right now. I am taking a java class in school, but from what I understand C++ is 10000 times better.

[Elijah]

[/CODE]

The point is that the number of digits in a number equals the number of times you can divide this number by 10 plus one.

100/10 = 10;
10/10 = 1;
1/10 = 0;

100 can be divided by 10 two times. Two + one = three.
The number of digits in 100 is three. [/B][/QUOTE]
fired up my calcoo to try it out, how about 59? which supposed to have 34 digits, I think the algorithm there will check each number while it increments (?) might take some time if we're trying to find out billions? :confused:

[elderdays]

OK, how many Linux users does it take to......

I think I misunderstood too. The way I had it left him with the number he started with I think. I'm so confused.

One thing I do know, 100 can be divided by 10 two times. is not a true statement (from above). I'm going to try this with my newfound java "skills".

[bwkaz]

What the question seems to be asking is not "how many digits are in this number?", but rather, "what is the sum of the number of digits in each number, up to and including this one?"

For example, for 5, you have 1 digit in each of 1, 2, 3, 4, & 5. So the total is 5.

What they're saying up higher is not that 59 has 34 "digits", but rather that if you are given that the number has 59 "digits", you are supposed to come up with 34. 34 has 59 "digits".

This is because there is one digit in each of 1-9 (for a total of 9), and two digits in each of 10-34, for a total of 50 (there are 25 numbers from 10 to 34 inclusive). The sum is 59.

In 11, there is 1 digit in each of 1-9 (9 total), plus 2 digits in 10, plus 2 more in 11, for a sum of 13.

It is this mapping that my program is calculating. The ACM contest problem was to program the inverse mapping, and I don't know offhand whether that's possible or not (though I'd assume it is...).

I do know my programs both work with the forward mapping (number -> "digits") on all the test data. The first one's slow, but they both work. The inverse mapping I don't know how to do, but if I thought long enough, I might be able to come up with something.

[Elijah]

Originally posted by bwkaz
"what is the sum of the number of digits in each number, up to and including this one?"

That's the one :) , I'm still looking up the others way of tackling this, haven't yet checked your code yet though. Let's see ...

[Elijah]

fast fact:
for this particular problem (second one actually), there are:
113 submissions
79 solutions passed
11 minutes fastest solution :eek:
69.9% highest percentage of correct submissions
% teams solving the problem = 78.2%

I'm quite surprised it only took 11 minutes to some on solving this problem ... oh well :) I still need some improvement.

[Hena]

Bugger. I seemed to have more errors in my version. Can't seem to get it right without doing it, compiling it and making sure its right. So version number 3. Whole c code, so you need to change it to c++. Also with gcc and c, it need "-lm" for the pow.

Main bits to improve.
1. Use unsigned long instead of long, can use higher values.
2. Make some checking, so that if value is larger than long (or unsigned long) can handle, it gives out nice message.

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

long count_digits (long given);

int main () {
long dig,i;

i=10;
dig=count_digits(i);
printf ("1. %ld\n",dig);
i=34;
dig=count_digits(i);
printf ("2. %ld\n",dig);
i=222984739;
dig=count_digits(i);
printf ("2. %ld\n",dig);
return 0;
}

long count_digits (long given) {
long i=0,value=given,ret=0;

while (value>=10) {
value=value/10;
i++;
}

value=given;
for (;i>=0;i--) {
given=given-9*pow(10,i-1);
if (i) {
ret+=given*(i+1);
value=given=value-given;
} else {
ret+=value;
}
}
return ret;
}



Ps. If this is still wrong, then duh...

[Elijah]

Originally posted by Hena
Ps. If this is still wrong, then duh...
Thanks for trying, yes it's working .. but you got it backwards. If I changed the first given to 11, it must output 10 ... not 13. If I changed some given to 13, should output 11. The number 59 should give 34 not the other way around. Like bwkaz says, we're doing it inverse. But you got the idea now, seems faster than mine but pretty close. :)

THANKS to everyone for the input :p I think I can manage to come up with something from this point in :p

[Elijah]

Originally posted by bwkaz
Here we go, here's a better (read: quicker) way to do it.

First, notice that if you clamp the number (call it i) down to some multiple of 10, it becomes easy to count what you call digits. There are 9 1-digit numbers (that are counted), 90 2-digit numbers, and 900 3-digit numbers. Etc., etc.

So, you figure out how "big" the number you're going up to is. For example, 3000 would get a value of 1000 for this, since 1000 is the largest power of 10 less than 3000.

Then, we can easily figure out the sum up to that "big"ness value. When the value is 1000, the "sum" is 1*9 + 2*90 + 3*900. It's the sum of (9*i)*10^(i-1), for values of i from 1 to log-base-10 of "big"ness.

So calculate that sum, that's what I'm doing here in the for loop. Set the counter to that value.

Then, you still have (for example) 1000 up through 3000 to count. All of these numbers have the same number of digits, 4, and you can do a bit of simple math (3000 - 1000 + 1) to figure out how many there are. Multiply this by the number of digits in them, and add that to the counter.

Then, counter is the value you wanted.

We don't even need to use log10()! :)

int main()
{
// Finds the number of your definition of "digits" in NUMBER:
const int NUMBER=101;
int counter=0;
int i = NUMBER;
int j, k;
int bigness = 1;

// get bigness to be the "bigness" value of i, the largest power
// of 10 that's <= i.

while(bigness <= NUMBER/10)
bigness *= 10;

// There are 9 single-digit numbers, 90 double-digit ones,
// etc., etc. So multiply the number of numbers by the
// number of digits in each, and add that to counter.
//
// k is the number of digits in each

for(j=1,k=1; j<bigness; j*=10,k++) {
counter += (9 * j) * k;
}

// counter includes all the numbers up to bigness-1, no more.

// Subtracting off (bigness-1) will take away all the numbers
// that we've already counted.

i -= (bigness-1);

// And what's left in i is the number of numbers left to count.
// k is the number of digits in each of them, because it's the
// number of digits in bigness (and in i).

counter += i * k;

printf("The number of \"digits\" in %d is %d.\n", NUMBER, counter);

return 0;
} If there's any part of the math that doesn't make any sense, I can try to explain it.
oops, output of 11 is 13, I'll see if I can reverse it. Thanks :)

[Hena]

Originally posted by Elijah
Thanks for trying, yes it's working .. but you got it backwards.
ROFL :D

Oh well. So it needs to be working ather way around, but idea is sound under it. Bwkaz has it nicer though :).

[infidel]

Greetings everyone,

I don't know if you have found a soution to this yet but here's one:


#include <iostream>

using std::cout;
using std::cin;
using std::endl;

#ifdef _MSC_VER
typedef __int64 int64;
#else
typedef long long int64;
#endif

long power(long base, long exp)
{
return (exp)?base*power(base,exp-1) : 1;
}

long calc_pages(int64 digits)
{
if (digits < 10)
return digits;

int64 g, d, p, k;

g = d = p = k = 0;

do {
k = 9*power(10,g);
if (k*(g+1) < digits) {
d += k*(g+1);
p += k;
} else {
break;
}
++g;
} while (1);

if ((digits - d) % (g+1) != 0) return -1; // Impossible
else return ((digits - d) / (g+1)) + p;
}

int main()
{
int64 digits,res;

do {
cout << endl << "Enter digits: ";
cin >> digits;
res = calc_pages(digits);
cout << "Pages: ";
if (res ==-1) cout << "Impossible";
else cout << res;
cout << endl;
} while (digits > 0);

return 0;
}


Running the program:

Enter digits: 11
Pages: 10
Enter digits: 13
Pages: 11
Enter digits: 59
Pages: 34
Enter digits: 60
Pages: Impossible
Enter digits: 1999999998
Pages: 234567900
Enter digits: 0
Pages: 0

Note: I used 64 bit ints to avoid overflow, wich was happening for the '1999999998'. Maybe it could be avoided with a better algorithm!