limits reached

[O.R.Senthil Kumaran]

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/

 

[Artie Gold]

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

 

[O.R.Senthil Kumaran]

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/

 

[Artie Gold]

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

 

[Jack Klein]

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?

 

[Chris Torek]

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.

 

[Artie Gold]

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

 

[Brett Frankenberger]

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
will return the correct answer.

-- Brett

 

[Jonathan Adams]

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.
As someone else already pointed out, your printf() output is being
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
your output code, not your algorithm.

Cheers,
- jonathan

 

[Chris Torek]

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

Oops, quite right. I missed the "static" completely!

 

[Robert Gamble]

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
thinking about submitting the GLAT

That said, there are a few very simple ways to go about this and it
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

 

[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
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