Ben FM Ben FM - 22 days ago 7
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?

Answer

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