1votos

Números especiales en C

por josejuan hace 4 años

Es posible obtener todos los especiales hasta `n` en tiempo O(log n) y espacio O(log n).

Un número es especial cuando el número de números mayores que 1 y menores o iguales a él mismo que contienen algún dígito con uno es el mismo que aquellos que no contienen ningún dígito 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <inttypes.h> 
 
#define I128 __int128 
 
I128 pot10 [30]; 
 
I128 bajoPot [] = { 
    /* x( 0) = */  0 
    /* x( 1) = */, 1 
    /* x( 2) = */, 19 
    /* x( 3) = */, 271 
    /* x( 4) = */, 3439 
    /* x( 5) = */, 40951 
    /* x( 6) = */, 468559 
    /* x( 7) = */, 5217031 
    /* x( 8) = */, 56953279 
    /* x( 9) = */, 612579511 
    /* x(10) = */, 6513215599 
    /* x(11) = */, 68618940391 
    /* x(12) = */, 717570463519 
    /* x(13) = */, 7458134171671 
    /* x(14) = */, 77123207545039 
    /* x(15) = */, 794108867905351 
    /* x(16) = */, 8146979811148159 
    /* x(17) = */, 83322818300333431 
    /* x(18) = */, 849905364703000879 
    /* x(19) = */, 864914828232700791 //1 
    /* x(20) = */, 878423345409430711 //99 
    /* x(21) = */, 890581010868487640 //791 
    /* x(22) = */, 901522909781638876 //7119 
    /* x(23) = */, 911370618803474989 //04071 
    /* x(24) = */, 920233556923127490 //136639 
    /* x(25) = */, 928210201230814741 //1229751 
}; 
 
I128 digits2int(char *d, int n) { 
    I128 p = 1, s = 0; 
    int i; 
    for (i = 0; i < n; i++) { 
        s += p * d[i]; 
        p *= 10; 
    return s; 
 
void printI128(I128 n) { 
    if(n < 1) return; 
    printI128(n / 10); 
    printf("%i", n % 10); 
void printI128n(I128 n) { 
    if(n < 10) printf("%i\n", (int)n); 
    printI128(n); printf("\n"); 
 
int main(int argc, char **argv) { 
    int digits = atoi(argv[1]); 
    I128 con = 0; 
    I128 sin = 0; 
    {int i; pot10[0] = 1; for(i = 1; i < 30; i++) pot10[i] = 10 * pot10[i - 1]; } // imposible fijar constantes tan grandes 
    bajoPot[19] = bajoPot[19] * 10 + 1; 
    bajoPot[20] = bajoPot[20] * 100 + 99; 
    bajoPot[21] = bajoPot[21] * 1000 + 791; 
    bajoPot[22] = bajoPot[22] * 10000 + 7119; 
    bajoPot[23] = bajoPot[23] * 100000 + 4071; 
    bajoPot[24] = bajoPot[24] * 1000000 + 136639; 
    bajoPot[25] = bajoPot[25] * 10000000 + 1229751; 
 
    char *D = (char *) malloc(digits); 
    memset(D, 0, digits); 
    for (;;) { 
            { // incrementamos 
                int d = 0; 
                for (;;) { 
                    char c = D[d]; 
                    if (c == 0) { 
                        // incrementar un 0 es que a la derecha había todo 9999 
                        I128 con2 = con + pot10[d]; 
                        D[d] = 1; 
                        if (con < sin && sin <= con2) { 
                            I128 n = digits2int(D, digits) + sin - con - 1; 
                            printI128n(n); 
                        con = con2; 
 
                        {int j; for (j = 0; j < d; j++) D[j] = 9; } 
                        // intentaremos incrementar todos los `sin` posibles 
                        // estamos en 19..9 ¿podemos pasar a 29..9 siendo aún sin<con? ¿y a 39..9?, ¿y a... 
                        if(d>1){ 
                            char j; 
                            I128 con0 = con; 
                            for (j = 2; j < 10; j++) { 
                                I128 sin2 = sin + pot10[d] - bajoPot[d]; 
                                if (sin2 < con0) { // si incrementando sólo los "sin" sigue siendo menor, imposible que iguale 
                                    D[d] = j; 
                                    sin = sin2; 
                                    con += bajoPot[d]; 
                                else { 
                                    break; // habrá que seguir por debajo 
 
                        break; 
                    else { 
                        if (c == 9) { 
                            D[d] = 0; 
                            d++; 
                            if (d == digits) { 
                                goto end0; 
                        else { 
                            if (d == 0) { 
                                // estamos en el dígito 1, 2, 3, 4, 5, 6, 7 u 8 pasaremos directamente al 9 
                                char inc = 9 - D[d]; 
                                I128 sin2 = sin + inc; 
                                if (sin < con && con <= sin2) { 
                                    I128 n = digits2int(D, digits) + con - sin; 
                                    printI128n(n); 
                                sin = sin2; 
                                D[d] = 9; 
                                break; 
                            else { 
                                D[d]++; 
                                sin++; 
                                if (con == sin) { 
                                    printI128n(digits2int(D, digits)); 
                                break; 
end0:; 
return 0; 
 
/* 
 
# en un Intel Atom revisando hasta 10^23 
 
josejuanSolveet$ time -f "%E, %M" ./a.out 23 
16 
24 
160 
270 
272 
1456 
3398 
3418 
3420 
3422 
13120 
44686 
118096 
674934 
1062880 
0:00.00, 1376 
 
 
*/ 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.