<< problem 155 - Counting Capacitor Circuits | Exploring strings for which only one character ... - problem 158 >> |
Problem 156: Counting Digits
(see projecteuler.net/problem=156)
Starting from zero the natural numbers are written down in base 10 like this:
0 1 2 3 4 5 6 7 8 9 10 11 12....
Consider the digit d=1. After we write down each number n, we will update the number of ones that have occurred and call this number f(n,1).
The first values for f(n,1), then, are as follows:
nf(n,1)
00
11
21
31
41
51
61
71
81
91
102
114
125
Note that f(n,1) never equals 3.
So the first two solutions of the equation f(n,1)=n are n=0 and n=1. The next solution is n=199981.
In the same manner the function f(n,d) gives the total number of digits d that have been written down after the number n has been written.
In fact, for every digit d != 0, 0 is the first solution of the equation f(n,d)=n.
Let s(d) be the sum of all the solutions for which f(n,d)=n.
You are given that s(1)=22786974071.
Find sum{s(d)} for 1 <= d <= 9.
Note: if, for some n, f(n,d)=n for more than one value of d this value of n is counted again for every value of d for which f(n,d)=n.
My Algorithm
First I wrote a brute-force function countSingle
that counts a digit in a single number.
Obviously it's not the fastest approach to this problem, since s(1) = 22786974071 ...
Nevertheless, countSingle
can be used to analyze all numbers and digits up to a million.
And a certain pattern appeared:
digit<10<100<1000<10000
11203004000
21203004000
31203004000
41203004000
51203004000
61203004000
71203004000
81203004000
91203004000
Each number x can be split into its parts (I don't want to use the word "digits" here ...), e.g. 5684 = 5 * 10^3 + 6 * 10^2 + 8 * 10^1 + 4 * 10^0.
And the same can be done with the digit-counting function f(5684, i) = f(5000, i) + f(600, i) + f(80, i) + f(4, i)
My function count
basically does exactly that: it split a number into its parts and counts how often each digit occurs:
- find the left-most part by slowly multiplying
shift
by 10 - increment
multiplier
as well, it will be the number shown in the table above
digit
, then the count is 1.A number between 10 and 99 (inclusive) requires some work:
- if the leading part is smaller than
digit
, thendigit
doesn't appear there - if the leading part is larger than
digit
, thendigit
appeared 10x at that position - if the leading part is equal to
digit
, thendigit
appeared as often as the right-most part plus 1 - add the
multiplier
multiplied by the leading part - recursively call the function with the right-most part only, add the count to the current
result
multiplier
by the left-most digit.And f(84, 8) = 4 + 1 + 8 * 1 = 13 because 8 can be found 4+1 in the left-most digit (80, 81, 82, 83, 84) and 8x in the right-most digit.
Finally f(84, 7) = 10 + 8 * 1 = 19 because 7 can be found 10x in the left-most digit and 8x in the right-most digit.
Now I have a pretty fast function to count a single digit in a huge range of numbers, but where does that range end ?
I create some test code and looked at the results of f(n, d) / n for n = 10^i (→ all powers of ten) and observed that the ratio exceeds 1 for 10^10.
Since my code is fast, I decided to add some safety margin and set
Limit = 10^12
(actually the highest number for any f(n, d) = n is n = 80000000001).Binary search is my tool to find all numbers n such that f(n, d) = n:
- n is strictly monotonically increasing
- f(n, d) is monotonically increasing
- find the center of the current range [from, to] so that center = dfrac{from + to}{2}
- only if f(center, d) >= from and center >= f(from, d) then there could be a number n in that range [from, center] where f(n, d) = n
- similar logic applies for f(to, d) >= center and to >= f(center, d)
- if the search narrows down the range to a single number then check if f(n, d) = n
Modifications by HackerRank
The base can be between 2 and 10 and the analyzed digits can be modified by the user (instead of always computing s(1) + s(2) + ... + s(9)).
I totally forgot about looking for a proper Limit
depending on base
but 10^12 worked perfectly fine for all test cases. Lucky me !
Interactive test
You can submit your own input to my program and it will be instantly processed at my server:
This live test is based on the Hackerrank problem.
This is equivalent toecho "10 1 1" | ./156
Output:
Note: the original problem's input 10 9 1 2 3 4 5 6 7 8 9
cannot be entered
because just copying results is a soft skill reserved for idiots.
(this interactive test is still under development, computations will be aborted after one second)
My code
… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too.
The code contains #ifdef
s to switch between the original problem and the Hackerrank version.
Enable #ifdef ORIGINAL
to produce the result for the original problem (default setting for most problems).
#include <iostream>
// decimal => 10
unsigned int base = 10; // change only for modified Hackerrank problem
// count digits in a single number
unsigned int countSingle(unsigned int digit, unsigned long long value)
{
// actually the problem doesn't ask for zeros, so I could skip this special treatment of zeros ...
if (value == 0 && digit == 0)
return 1;
unsigned int result = 0;
while (value > 0)
{
if (value % base == digit)
result++;
value /= base;
}
return result;
}
// return f(value, digit)
unsigned long long count(unsigned int digit, unsigned long long value)
{
// handle a single digit
if (value < base)
return value < digit ? 0 : 1;
// find highest digit
unsigned long long shift = 1;
unsigned long long multiplier = 0;
while (shift * base <= value)
{
shift *= base;
multiplier++;
}
multiplier *= shift / base;
// split number: "first" represents the left-most digit and "remainder" is everything else
auto first = value / shift;
auto remainder = value % shift;
// count digit in "remainder"
auto result = first * multiplier; // full blocks
result += count(digit, remainder); // partial block
// count digit in "first"
if (digit == first)
result += remainder + 1;
if (digit < first && digit > 0) // I don't need to handle zero, but it felt wrong ...
result += shift;
return result;
}
// return sum of all numbers from <= x <= to where count(x, digit) = x
unsigned long long findAll(unsigned int digit, unsigned long long from, unsigned long long to)
{
// narrowed down to a single number ?
auto center = (from + to) / 2;
if (from == center)
{
auto current = count(digit, from);
if (current == from)
return from;
else
return 0;
}
unsigned long long result = 0;
auto countFrom = count(digit, from);
#define FAST
#ifdef FAST
// matches often occur in bunches, try to resolve many at once
while (countFrom == from && from < to)
{
result += from;
countFrom += countSingle(digit, ++from);
}
if (from >= to + 1)
return result;
#endif
center = (from + to) / 2;
// binary subdivision
auto countCenter = count(digit, center);
auto countTo = count(digit, to);
// recursive search in lower half
if (countCenter >= from && center >= countFrom && center > from)
result += findAll(digit, from, center);
// recursive search in upper half
if (countTo >= center && to >= countCenter && center < to)
result += findAll(digit, center, to);
return result;
}
int main()
{
// 10^12
const auto Limit = 1000000000000ULL; // actually 80000000001 would suffice
// will store the result
unsigned long long sum = 0;
//#define ORIGINAL
#ifdef ORIGINAL
for (unsigned int digit = 1; digit < base; digit++)
sum += findAll(digit, 0, Limit);
#else
unsigned int tests;
std::cin >> base >> tests;
// read all digits and count them
while (tests--)
{
unsigned int digit;
std::cin >> digit;
sum += findAll(digit, 0, Limit);
}
#endif
// done !
std::cout << sum << std::endl;
return 0;
}
This solution contains 23 empty lines, 20 comments and 7 preprocessor commands.
Benchmark
The correct solution to the original Project Euler problem was found in 0.01 seconds on an Intel® Core™ i7-2600K CPU @ 3.40GHz.
(compiled for x86_64 / Linux, GCC flags: -O3 -march=native -fno-exceptions -fno-rtti -std=gnu++11 -DORIGINAL
)
See here for a comparison of all solutions.
Note: interactive tests run on a weaker (=slower) computer. Some interactive tests are compiled without -DORIGINAL
.
Changelog
October 6, 2017 submitted solution
October 6, 2017 added comments
Hackerrank
see https://www.hackerrank.com/contests/projecteuler/challenges/euler156
My code solves 33 out of 33 test cases (score: 100%)
Difficulty
Project Euler ranks this problem at 70% (out of 100%).
Hackerrank describes this problem as medium.
Note:
Hackerrank has strict execution time limits (typically 2 seconds for C++ code) and often a much wider input range than the original problem.
In my opinion, Hackerrank's modified problems are usually a lot harder to solve. As a rule thumb: brute-force is rarely an option.
Links
projecteuler.net/thread=156 - the best forum on the subject (note: you have to submit the correct solution first)
Code in various languages:
Python github.com/HaochenLiu/My-Project-Euler/blob/master/156.py (written by Haochen Liu)
Python github.com/Meng-Gen/ProjectEuler/blob/master/156.py (written by Meng-Gen Tsai)
Python github.com/smacke/project-euler/blob/master/python/156.py (written by Stephen Macke)
C++ github.com/roosephu/project-euler/blob/master/156.cpp (written by Yuping Luo)
Java github.com/thrap/project-euler/blob/master/src/Java/Problem156.java (written by Magnus Solheim Thrap)
Perl github.com/shlomif/project-euler/blob/master/project-euler/156/euler-156-v2.pl (written by Shlomi Fish)
Those links are just an unordered selection of source code I found with a semi-automatic search script on Google/Bing/GitHub/whatever.
You will probably stumble upon better solutions when searching on your own. Maybe not all linked resources produce the correct result and/or exceed time/memory limits.
Heatmap
Please click on a problem's number to open my solution to that problem:
green | solutions solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too | |
yellow | solutions score less than 100% at Hackerrank (but still solve the original problem easily) | |
gray | problems are already solved but I haven't published my solution yet | |
blue | solutions are relevant for Project Euler only: there wasn't a Hackerrank version of it (at the time I solved it) or it differed too much | |
orange | problems are solved but exceed the time limit of one minute or the memory limit of 256 MByte | |
red | problems are not solved yet but I wrote a simulation to approximate the result or verified at least the given example - usually I sketched a few ideas, too | |
black | problems are solved but access to the solution is blocked for a few days until the next problem is published | |
[new] | the flashing problem is the one I solved most recently |
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 | 174 | 175 |
176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 | 194 | 195 | 196 | 197 | 198 | 199 | 200 |
201 | 202 | 203 | 204 | 205 | 206 | 207 | 208 | 209 | 210 | 211 | 212 | 213 | 214 | 215 | 216 | 217 | 218 | 219 | 220 | 221 | 222 | 223 | 224 | 225 |
226 | 227 | 228 | 229 | 230 | 231 | 232 | 233 | 234 | 235 | 236 | 237 | 238 | 239 | 240 | 241 | 242 | 243 | 244 | 245 | 246 | 247 | 248 | 249 | 250 |
251 | 252 | 253 | 254 | 255 | 256 | 257 | 258 | 259 | 260 | 261 | 262 | 263 | 264 | 265 | 266 | 267 | 268 | 269 | 270 | 271 | 272 | 273 | 274 | 275 |
276 | 277 | 278 | 279 | 280 | 281 | 282 | 283 | 284 | 285 | 286 | 287 | 288 | 289 | 290 | 291 | 292 | 293 | 294 | 295 | 296 | 297 | 298 | 299 | 300 |
301 | 302 | 303 | 304 | 305 | 306 | 307 | 308 | 309 | 310 | 311 | 312 | 313 | 314 | 315 | 316 | 317 | 318 | 319 | 320 | 321 | 322 | 323 | 324 | 325 |
326 | 327 | 328 | 329 | 330 | 331 | 332 | 333 | 334 | 335 | 336 | 337 | 338 | 339 | 340 | 341 | 342 | 343 | 344 | 345 | 346 | 347 | 348 | 349 | 350 |
351 | 352 | 353 | 354 | 355 | 356 | 357 | 358 | 359 | 360 | 361 | 362 | 363 | 364 | 365 | 366 | 367 | 368 | 369 | 370 | 371 | 372 | 373 | 374 | 375 |
376 | 377 | 378 | 379 | 380 | 381 | 382 | 383 | 384 | 385 | 386 | 387 | 388 | 389 | 390 | 391 | 392 | 393 | 394 | 395 | 396 | 397 | 398 | 399 | 400 |
401 | 402 | 403 | 404 | 405 | 406 | 407 | 408 | 409 | 410 | 411 | 412 | 413 | 414 | 415 | 416 | 417 | 418 | 419 | 420 | 421 | 422 | 423 | 424 | 425 |
426 | 427 | 428 | 429 | 430 | 431 | 432 | 433 | 434 | 435 | 436 | 437 | 438 | 439 | 440 | 441 | 442 | 443 | 444 | 445 | 446 | 447 | 448 | 449 | 450 |
451 | 452 | 453 | 454 | 455 | 456 | 457 | 458 | 459 | 460 | 461 | 462 | 463 | 464 | 465 | 466 | 467 | 468 | 469 | 470 | 471 | 472 | 473 | 474 | 475 |
476 | 477 | 478 | 479 | 480 | 481 | 482 | 483 | 484 | 485 | 486 | 487 | 488 | 489 | 490 | 491 | 492 | 493 | 494 | 495 | 496 | 497 | 498 | 499 | 500 |
501 | 502 | 503 | 504 | 505 | 506 | 507 | 508 | 509 | 510 | 511 | 512 | 513 | 514 | 515 | 516 | 517 | 518 | 519 | 520 | 521 | 522 | 523 | 524 | 525 |
526 | 527 | 528 | 529 | 530 | 531 | 532 | 533 | 534 | 535 | 536 | 537 | 538 | 539 | 540 | 541 | 542 | 543 | 544 | 545 | 546 | 547 | 548 | 549 | 550 |
551 | 552 | 553 | 554 | 555 | 556 | 557 | 558 | 559 | 560 | 561 | 562 | 563 | 564 | 565 | 566 | 567 | 568 | 569 | 570 | 571 | 572 | 573 | 574 | 575 |
576 | 577 | 578 | 579 | 580 | 581 | 582 | 583 | 584 | 585 | 586 | 587 | 588 | 589 | 590 | 591 | 592 | 593 | 594 | 595 | 596 | 597 | 598 | 599 | 600 |
601 | 602 | 603 | 604 | 605 | 606 | 607 | 608 | 609 | 610 | 611 | 612 | 613 | 614 | 615 | 616 | 617 | 618 | 619 | 620 | 621 | 622 | 623 | 624 | 625 |
626 | 627 | 628 | 629 | 630 | 631 |
I scored 13526 points (out of 15700 possible points, top rank was 17 out of ≈60000 in August 2017) at Hackerrank's Project Euler+.
My username at Project Euler is stephanbrumme while it's stbrumme at Hackerrank.
Look at my progress and performance pages to get more details.
Copyright
I hope you enjoy my code and learn something - or give me feedback how I can improve my solutions.
All of my solutions can be used for any purpose and I am in no way liable for any damages caused.
You can even remove my name and claim it's yours. But then you shall burn in hell.
The problems and most of the problems' images were created by Project Euler.
Thanks for all their endless effort !!!
<< problem 155 - Counting Capacitor Circuits | Exploring strings for which only one character ... - problem 158 >> |