# limits reached

Discussion in 'C Programming' started by O.R.Senthil Kumaran, Oct 24, 2004.

1. ### O.R.Senthil KumaranGuest

Hi all,
I am trying with the following Question:
Q: Consider a function which, for a given whole number n, returns the
number of ones required when writing out all numbers between 0 and n. For
eg: f(13)=6. Notice that f(1)=1.

What is the next largest n such that f(n) =n.

To solve this, I wrote the following program:

#include<limits.h>
#include<stdio.h>
int main(void)
{
unsigned long long int i,n,count;
for(i=1;i<=ULLONG_MAX;i++)
{
count=0;
while((n=(i%10))>10)
{
if(n==1)
count++;
i/=10;
}
if (n == 1)
count++;
if( i == count)
printf("%llu",i);
}
}

But, the program (a.out) is running for more than 45 minutes! now without
any output.
Is it feasible to try out such a program? How should I approach this
otherwise?

Regards,
Senthil

http://sarovar.org/projects/uthcode/

O.R.Senthil Kumaran, Oct 24, 2004

2. ### Artie GoldGuest

O.R.Senthil Kumaran wrote:
> Hi all,
> I am trying with the following Question:
> Q: Consider a function which, for a given whole number n, returns the
> number of ones required when writing out all numbers between 0 and n. For
> eg: f(13)=6. Notice that f(1)=1.
>
> What is the next largest n such that f(n) =n.
>
> To solve this, I wrote the following program:
>
> #include<limits.h>
> #include<stdio.h>
> int main(void)
> {
> unsigned long long int i,n,count;
> for(i=1;i<=ULLONG_MAX;i++)
> {
> count=0;
> while((n=(i%10))>10)
> {
> if(n==1)
> count++;
> i/=10;
> }
> if (n == 1)
> count++;
> if( i == count)
> printf("%llu",i);
> }
> }
>
> But, the program (a.out) is running for more than 45 minutes! now without
> any output.
> Is it feasible to try out such a program? How should I approach this
> otherwise?
>

Hint: What is the value of ULLONG_MAX on your implementation?

HTH,
--ag

--
Artie Gold -- Austin, Texas

"If you don't think it matters, you're not paying attention."

Artie Gold, Oct 24, 2004

3. ### O.R.Senthil KumaranGuest

On Sun, 24 Oct 2004 15:39:43 -0500, Artie Gold wrote:
> Hint: What is the value of ULLONG_MAX on your implementation?

Maximum value - Unsigned long long int : 18446744073709551615

Well, the program I posted initially was a wrong one. For the above
problem, here is the correct program:

/*Consider a function which, for a given whole number n, returns the
number of ones required when writing out all numbers between 0 and n. For
eg: f(13)=6. Notice that f(1)=1.
What is the next largest n such that f(n) =n */

#include<limits.h>
#include<stdio.h>
unsigned long long int countones(unsigned long long int); int main(void)
{
unsigned long long int i,cn;

for(i = 1; i<= ULLONG_MAX; ++i)
{
cn = countones(i);
if( i == cn)
printf("%d",i);
}

return 0;
}

unsigned long long int countones(unsigned long long int i) {
static unsigned long long int count = 0; int digit;

while((i/10) >= 1)
{
digit = i % 10;

if(digit == 1)
count++;
i /= 10;
}
if( i == 1)
count++;

return count;
}
The problem still remains,I understand unsigned long long integer is a
HUGE number, but I would like to try out till the limits to get the
solution to this problem. It is taking a long time and I have not
reached the end of execution yet!(leave alone the results). Do you have
any alternative to try out this?

Senthil

http://sarovar.org/projects/uthcode/

O.R.Senthil Kumaran, Oct 24, 2004
4. ### Artie GoldGuest

O.R.Senthil Kumaran wrote:
> On Sun, 24 Oct 2004 15:39:43 -0500, Artie Gold wrote:
>
>>Hint: What is the value of ULLONG_MAX on your implementation?

>
>
> Maximum value - Unsigned long long int : 18446744073709551615

This is (as you state below) a HUGE number.
>
> Well, the program I posted initially was a wrong one. For the above
> problem, here is the correct program:
>
> /*Consider a function which, for a given whole number n, returns the
> number of ones required when writing out all numbers between 0 and n. For
> eg: f(13)=6. Notice that f(1)=1.
> What is the next largest n such that f(n) =n */
>
> #include<limits.h>
> #include<stdio.h>
> unsigned long long int countones(unsigned long long int); int main(void)
> {
> unsigned long long int i,cn;
>
> for(i = 1; i<= ULLONG_MAX; ++i)
> {
> cn = countones(i);
> if( i == cn)
> printf("%d",i);

Try:
{
printf("%d ", i);
fflush(stdout);
}
otherwise you will see no output -- and Bad Things are likely to happen
first.

> }
>
> return 0;
> }
>
> unsigned long long int countones(unsigned long long int i) {
> static unsigned long long int count = 0; int digit;
>
> while((i/10) >= 1)
> {
> digit = i % 10;
>
> if(digit == 1)
> count++;
> i /= 10;
> }
> if( i == 1)
> count++;
>
> return count;
> }
> The problem still remains,I understand unsigned long long integer is a
> HUGE number, but I would like to try out till the limits to get the
> solution to this problem. It is taking a long time and I have not
> reached the end of execution yet!(leave alone the results). Do you have
> any alternative to try out this?

Right.

You are executing the loop approximately (4 billion x 4 billion) times.
4 billion seconds is approxiamtely 120 *years*.

Do you see the problem?

HTH,
--ag

--
Artie Gold -- Austin, Texas

"If you don't think it matters, you're not paying attention."

Artie Gold, Oct 24, 2004
5. ### Jack KleinGuest

On Mon, 25 Oct 2004 02:45:00 +0500, "O.R.Senthil Kumaran"
<> wrote in comp.lang.c:

> On Sun, 24 Oct 2004 15:39:43 -0500, Artie Gold wrote:
> > Hint: What is the value of ULLONG_MAX on your implementation?

>
> Maximum value - Unsigned long long int : 18446744073709551615
>
> Well, the program I posted initially was a wrong one. For the above
> problem, here is the correct program:
>
> /*Consider a function which, for a given whole number n, returns the
> number of ones required when writing out all numbers between 0 and n. For
> eg: f(13)=6. Notice that f(1)=1.
> What is the next largest n such that f(n) =n */
>
> #include<limits.h>
> #include<stdio.h>
> unsigned long long int countones(unsigned long long int); int main(void)
> {
> unsigned long long int i,cn;
>
> for(i = 1; i<= ULLONG_MAX; ++i)

Since the subtle hint did not work, let's try the not-so-subtle hint.

Your loop will end when 'long long int i' holds a value GREATER than
ULLONG_MAX.

If you still don't get it, reread the sentence above slowly.

Hint:

long long int i = ULLONG_MAX;

++i;

What is the value of 'i'? It is GREATER than ULLONG_MAX?

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html

Jack Klein, Oct 24, 2004
6. ### Chris TorekGuest

>On Sun, 24 Oct 2004 15:39:43 -0500, Artie Gold wrote:
>> Hint: What is the value of ULLONG_MAX on your implementation?

In article <>
O.R.Senthil Kumaran <> wrote:
>Maximum value - Unsigned long long int : 18446744073709551615

OK, now, what happens when i (a variable of type "unsigned long
long") is equal to 18446744073709551615, and the loop executes the
"i++" instruction? What is the new value in i? (Remember that
unsigned arithmetic is modular or "clock" arithmetic, much as on
a 12-hour clock, the hours count 1,2,3,...,9,10,11,12,1,2,3,... so
that 12+1 = 1.)

>... here is the correct program:

The program still has a bug: your function countones() returns the
number of '1' digits in the decial expansion of its argument. The
the problem specifies:

_n_
\
f(n) = > countones(i)
/__
i = 1

but you call countones() only for one number; you need to compute
the sum of countones() for n numbers (for a brute-force solution,
which is clearly not the best possible solution).

A hint for a "better" solution: consider any expansion of some
number i, expressed in base b, as a series of terms:

k k-1 1
d b + d b + ... + d b + d
k k-1 1 0

For instance, i=175 in base 10 is 1(100) + 7(10) + 5. Here
countones(i) is 1 (because there is one "1" digit, for ten squared,
in the hundreds place). We can immediately see that countones(i-1)
through countones(i-75) all have a 1 in the hundreds place -- so
we need only consider the tens and ones places in all the smaller
numbers. Once i exceeds 199 (up through 999 inclusive), however,
it will have a 2 or 3 or ... or 9 in the hundreds place. The only
contributions you can get to "1" digits will come from the tens and
ones places.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
Reading email is like searching for food in the garbage, thanks to spammers.

Chris Torek, Oct 24, 2004
7. ### Artie GoldGuest

Jack Klein wrote:
> On Mon, 25 Oct 2004 02:45:00 +0500, "O.R.Senthil Kumaran"
> <> wrote in comp.lang.c:
>
>
>>On Sun, 24 Oct 2004 15:39:43 -0500, Artie Gold wrote:
>>
>>>Hint: What is the value of ULLONG_MAX on your implementation?

>>
>>Maximum value - Unsigned long long int : 18446744073709551615
>>
>>Well, the program I posted initially was a wrong one. For the above
>>problem, here is the correct program:
>>
>>/*Consider a function which, for a given whole number n, returns the
>>number of ones required when writing out all numbers between 0 and n. For
>>eg: f(13)=6. Notice that f(1)=1.
>>What is the next largest n such that f(n) =n */
>>
>>#include<limits.h>
>>#include<stdio.h>
>>unsigned long long int countones(unsigned long long int); int main(void)
>>{
>> unsigned long long int i,cn;
>>
>> for(i = 1; i<= ULLONG_MAX; ++i)

>
>
> Since the subtle hint did not work, let's try the not-so-subtle hint.
>
> Your loop will end when 'long long int i' holds a value GREATER than
> ULLONG_MAX.
>
> If you still don't get it, reread the sentence above slowly.
>
> Hint:
>
> long long int i = ULLONG_MAX;
>
> ++i;
>
> What is the value of 'i'? It is GREATER than ULLONG_MAX?
>

Jack, the test in the code is `<='.

The question is, when will it even get that far?

Cheers,
--ag

--
Artie Gold -- Austin, Texas

"If you don't think it matters, you're not paying attention."

Artie Gold, Oct 24, 2004
8. ### Brett FrankenbergerGuest

In article <>,
Chris Torek <> wrote:
>
>but you call countones() only for one number; you need to compute
>the sum of countones() for n numbers (for a brute-force solution,
>which is clearly not the best possible solution).

"count" is declared static in countones(). As long as he calls
countones in order (countones(1), countones(2), ...), which he does, it

-- Brett

Brett Frankenberger, Oct 25, 2004

In article <>,
"O.R.Senthil Kumaran" <> wrote:

> Well, the program I posted initially was a wrong one. For the above
> problem, here is the correct program:

(put main on its own line, removed excess blank lines, added one or two
blank lines)

> /*Consider a function which, for a given whole number n, returns the
> number of ones required when writing out all numbers between 0 and n. For
> eg: f(13)=6. Notice that f(1)=1.
> What is the next largest n such that f(n) =n */
>
> #include<limits.h>
> #include<stdio.h>
> unsigned long long int countones(unsigned long long int);
>
> int main(void)
> {
> unsigned long long int i,cn;
>
> for(i = 1; i<= ULLONG_MAX; ++i)
> {
> cn = countones(i);
> if( i == cn)
> printf("%d",i);
> }
> return 0;
> }
>
> unsigned long long int countones(unsigned long long int i) {
> static unsigned long long int count = 0; int digit;
>
> while((i/10) >= 1)
> {
> digit = i % 10;
>
> if(digit == 1)
> count++;
> i /= 10;
> }
> if( i == 1)
> count++;
>
> return count;
> }

For what it's worth, it shouldn't take that long to get an answer.
Unless I did something wrong, I get an answer which easily fits in a
32-bit integer.

I'd recommend you clean up your code some; the use of "static" in
countones() is just asking for trouble -- main() should be doing the
summation. You loop is also more complex than it needs to be.
Something like:

while (i > 0) {
if ((i % 10) == 1)
count++;
i /= 10;
}
return (count);

is equivalent, easier to understand, and avoids the fix-up afterwards.
buffered -- you should do something like:

if (i == cn)
printf("%d\n", i);

Since stdout is line-buffered, this will guarantee a flush. Note that
you should get the output "1" immediately -- if you don't, investigate

Cheers,
- jonathan

10. ### Chris TorekGuest

>In article <>,
>Chris Torek <> wrote:
>>but you call countones() only for one number ...

In article <news:clhd8i\$54r\$>
Brett Frankenberger <> wrote:
>"count" is declared static in countones(). As long as he calls
>countones in order (countones(1), countones(2), ...), which he does, it

Oops, quite right. I missed the "static" completely!
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
Reading email is like searching for food in the garbage, thanks to spammers.

Chris Torek, Oct 25, 2004
11. ### Robert GambleGuest

On Mon, 25 Oct 2004 01:31:27 +0500, O.R.Senthil Kumaran wrote:

> Hi all,
> I am trying with the following Question:
> Q: Consider a function which, for a given whole number n, returns the
> number of ones required when writing out all numbers between 0 and n.
> For eg: f(13)=6. Notice that f(1)=1.
>
> What is the next largest n such that f(n) =n.
>
> To solve this, I wrote the following program:
>
> #include<limits.h>
> #include<stdio.h>
> int main(void)
> {
> unsigned long long int i,n,count;
> for(i=1;i<=ULLONG_MAX;i++)
> {
> count=0;
> while((n=(i%10))>10)
> {
> if(n==1)
> count++;
> i/=10;
> }
> if (n == 1)
> count++;
> if( i == count)
> printf("%llu",i);
> }
> }
>
> But, the program (a.out) is running for more than 45 minutes! now
> without any output.
> Is it feasible to try out such a program? How should I approach this
> otherwise?
>
> Regards,
> Senthil

I think that Google is looking for people that can solve this without
going to newgroups for help I might also add that as this is one of
the easiest questions on the test, you are in bad shape if you are

shouldn't take more than a fraction of a second for a well-written program
to come up with the answer, which is just under 200,000. You can also
solve this purely mathematically, without writing a program but it may
take longer depending on your level of competence in the area.

Out of purely educational interest, here is a simple program that will
find you the answer working in the same vein as your flawed offering:

#include <stdio.h>

int
main (void)
{
int ones = 6, i, n;
for (i = 14; i < 200000; ++i)
/* You want the first occurance ofter f(13)=6
* so initialize ones to 6 and start at 14 */
{
n = i;
while ( n > 0 )
{
if (n % 10 == 1) ++ones;
n /= 10;
}
if (i == ones)
{
printf("%d\n",ones);
return 0;
}
}
return 1;
}

Rob Gamble

Robert Gamble, Oct 25, 2004
12. ### SenthilGuest

Robert Gamble <> wrote in message
> I think that Google is looking for people that can solve this without
> going to newgroups for help I might also add that as this is one of
> the easiest questions on the test, you are in bad shape if you are
> thinking about submitting the GLAT

Yeah the problem was from GLAT (No 17). I tried and could devise the
brute force method of solving and it did. It was a practise for me in
C programming as well.
fflush(stdout) was the culprit, which did not print the number 199981!

But got interested in the other aspects like time taken inside the
loop which covers till ULLONG_MAX.

Nope, I am not thinking of submitting to GLAT, just enjoying it.

Thanks!
Senthil

Senthil, Oct 25, 2004