same as next_term(a_i, k, i, n) but computes terms without memoizing results.
(a_i, k, i, n)
| 107 | |
| 108 | |
| 109 | def compute(a_i, k, i, n): |
| 110 | """ |
| 111 | same as next_term(a_i, k, i, n) but computes terms without memoizing results. |
| 112 | """ |
| 113 | if i >= n: |
| 114 | return 0, i |
| 115 | if k > len(a_i): |
| 116 | a_i.extend([0 for _ in range(k - len(a_i))]) |
| 117 | |
| 118 | # note: a_i -> b * 10^k + c |
| 119 | # ds_b -> digitsum(b) |
| 120 | # ds_c -> digitsum(c) |
| 121 | start_i = i |
| 122 | ds_b, ds_c, diff = 0, 0, 0 |
| 123 | for j in range(len(a_i)): |
| 124 | if j >= k: |
| 125 | ds_b += a_i[j] |
| 126 | else: |
| 127 | ds_c += a_i[j] |
| 128 | |
| 129 | while i < n: |
| 130 | i += 1 |
| 131 | addend = ds_c + ds_b |
| 132 | diff += addend |
| 133 | ds_c = 0 |
| 134 | for j in range(k): |
| 135 | s = a_i[j] + addend |
| 136 | addend, a_i[j] = divmod(s, 10) |
| 137 | |
| 138 | ds_c += a_i[j] |
| 139 | |
| 140 | if addend > 0: |
| 141 | break |
| 142 | |
| 143 | if addend > 0: |
| 144 | add(a_i, k, addend) |
| 145 | return diff, i - start_i |
| 146 | |
| 147 | |
| 148 | def add(digits, k, addend): |