Ben FM - 1 year ago 78
C Question

Champernowne constant (Series of Integers) for C

I am prompted for a code to somehow print the series of Champernowne constant. (Actually work with it!)
so we want to find the n-th digit of such series:

`1234567891011121314...`

Here is my code:

`````` #include <stdio.h>

long long int num(long long int a);
long long int f(long long int n);
long long int power(long long int a, long long int b);
long long int dig(long long int a, long long int b);

/*MAIN*/

int main(void) {
long long int n = 0, k = 0, r = 0, m = 0;
/* n , num(n) , primary       result , range specifier */
scanf("%lld", &n);

k = num(n);
if (k <= 1) {
printf("%lld\n", n);
} else {
for (m = 0; n > f(power(10, m) - 1); m++) {
}

r = n - f(power(10, m - 1) - 1);

if (r % m == 0) {
printf("%lld\n", dig(power(10, m - 1) - 1 + r / m, 1));
} else {
printf("%lld\n",
dig(power(10, m - 1) - 1 + (int)r / m + 1, m + 1 - (r % m)));
}
}
return 0;
}

/*How many digits do we have ? */

long long int num(long long int a) {
long long int b = a;
long long int c = 0;
while (b != 0) {
b /= 10;
++c;
}
return c;
}

/* Power */
long long int power(long long int a, long long int b) {
if (b == 0) {
return 1L;
}
long long int c = 1;
long long int d;
d = a;
for (c = 1; c < b; c = c + 1) { a = a * d; }
return a;
}

/* Lets solve it! */
long long int f(long long int n) {
int k = num(n);
if (k == 1) { return n; }
return f(power(10, (k - 1)) - 1) + k * (n - (power(10, (k - 1)) - 1));
}

/*Digit */
long long int dig(long long int a, long long int b) {
long long int x = 0, z = 0, t = 0;
x = a % power(10, (b));
z = power(10, (b - 1));
t = x / z;
return t;
}
``````

But it has a gap I suppose, because it fails to pass 1 of the 7 test cases provided for it! Can anyone help me?

Your code is a little too complicated, I did not locate the problem, but I suspect you should decrement `n` by `f(power(10, m) - 1)` in your initial loop.

Here is a simpler program that can be customized for different bases and used from the command line or standard input:

``````#include <stdio.h>
#include <stdlib.h>

int digit(long long int pos, int base) {
int n = 1;            /* number of digits of the block numbers */
long long power = 1;  /* power of base at the start of the block */

if (pos <= 0)
return 0;

pos--;  /* adjust position such that 1st digit is 1 */
for (;;) {
/* length of the block of n-digit numbers */
long long int block = power * (base - 1) * n;
if (pos < block)
break;
pos -= block;
power *= base;
n++;
}
long long num = power + pos / n;
for (pos %= n; pos < n - 1; pos++) {
num /= base;
}
return (int)(num % base);
}

int main(int argc, char *argv[]) {
long long int n;
if (argc > 1) {
for (int i = 1; i < argc; i++) {
printf("%d\n", digit(strtoll(argv[i], NULL, 0), 10));
}
} else {
while (scanf("%lld", &n) == 1) {
printf("%d\n", digit(n, 10));
}
}
return 0;
}
``````

You can use a simple benchmark:

``````chqrlie@mac ~/dev/stackoverflow > ./champernowne {1..10000} | tr -d '\n' > c10000
``````

And verify that `c10000` contains the first 10000 digits of the Champernowne sequence.

You can also perform some verifications with the following programs:

generator.c:

``````#include <stdio.h>

int main(void) {
for (long long n = 1;; n++)
printf("%lld", n);
}
``````

extractor.c:

``````#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
if (argc > 1) {
long long i = 0, n = strtoll(argv[1], NULL, 0);
int c;
while ((c = getchar()) != EOF) {
if (++i == n) {
printf("%c\n", c);
break;
}
}
}
return 0;
}
``````

For example:

``````chqrlie@mac ~/dev/stackoverflow > time ./generator | ./extractor 1000000000
1

real    0m46.741s
user    1m6.978s
sys     0m0.759s

chqrlie@mac ~/dev/stackoverflow > time ./champernowne 1000000000
1

real    0m0.018s
user    0m0.003s
sys     0m0.004s
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download