Programmers are problem solvers, not code monkeys!
The following is a classical problem that is among the programming interview favorites at FAANG because it is best known for being the easiest hardest problem, a pun in the context of computational complexity theory, and because it is extremely deceptive, i.e., naive solutions work for typical test inputs, so they look like they work in general.
The Easiest Hardest Problem
A tyrannical king will close one of your bank accounts per day: it will choose two accounts, subtract their funds, close the smaller account, keep the difference in the larger account, and repeat this process daily until one account is left, which you keep.What is the largest sum of money that the king can take?
For example, if \$10, \$25, \$5, and \$60 are the funds in your 4 accounts, then
- on the first day, the king chooses the second (\$25) and fourth (\$60) accounts, closes the second account, and keeps the difference (\$60 - \$25 = \$35) in the fourth account, taking \$50;
- on the second day, the king chooses the first (\$10) and fourth (\$35) accounts, closes the first account, and keeps the difference (\$35 - \$10 = \$25) in the fourth account, taking \$20; and
- on the third day, the king chooses the third (\$5) and fourth (\$25) accounts, closes the third account, and keeps the difference (\$25 - \$5 = \$20) in the fourth account, taking \$10;
Here are four more examples:
Input: 703 840 51 (accounts)
Output: 1508 (largest sum of money the king can take)
Input: 51 100 200 249
Output: 600
Input: 26 5 10 831
Output: 82
Input: 925 148 411 961 451
Output: 2824
Here are three challenges for you:
Input: 492 315 270 460 603 233 201
Output: ?
Input: 363 393 393 572 70 292 657 353
Output: ?
Input: 306 287 222 217 425 171 110 442 525
Output: ?
Here is an ultimate challenge for you:
Input: 1715 50 1258 697 2130 1785 1164 553 1681 1991 2431 1334 2086 2203 2961 738 1854 25 2225 997 905 2345 2134 1649 1397 1320 372 1302 2650 2088 998 3125 2480 1539 1254 2965 2909 2737 145 1897 416 678 1075 2503 223 223 2974 1576 2789 1754 601 3068 153 946 2178 471 1717 2999 1811 967 27 1240 1566 2646 50 1012 3007 2164 667 1101 1459 915 1398 579 1839 2369 778 3211 1768 460 1621 1044 600 130 1786 1594 1818 958 2889 1244 542 685 734 1350 1957 1605 392 1003 842 3462 3700 1370 2613 2904 945 2826 317 2301 1037 1557 3542 722 3103 734 1080 1324 2809 916 1949 50 2671 1035 1117 295 176 386 1208 2657 391 341 3074 1381 1721 2590 1029 2033 1884 180 927 2736 966 2049 1826 3021 1995 1565 2070 3038 759 309 3100 454 1127 1409 2552 3045 2549 2080 2395 1171 516 640 1203 2862 2777 365 10 2159 2435 712 3319 1901 310 2023 3033 1344 971 1296 241 1154 1403 2110 412 2693 1257 937 2311 1171 1012 2591 1255 611 70 1635 50 2140 2050 882 3679 2441 2665 994 2543 2689 2408 732 2219 1711 48 1733 1551 10 2066 2477 380 237 657 2902 604 426 175 975 682 3072 1722 2140 116 918 543 1882 692 1451 1214 553 30 291 452 220 165 1015 1601 339 664 278 857 2544 523 30 2067 220 1572 392 100 2546 814 2090 1083 2163 659 416 2924 2801 1204 1566 1361 2295 2595 798 2872 2218 2256 1420 1673 1844 2800 493 1637 1020 1015 776 602 2362 1724 341 2081 426 2218 895 887 430 2010 1810 1805 645 3102 1428 1403 227 871 10 2311 2334 1495 1513 1349 2690 482 2488 2583 2377 1081 1481 2857 1340 644 1423 241 436 120 606 2373 3770 2305 2873 3006 1349 497 457 1547 2129 2016 2291 420 2321 505 2955 601 2937 1123 2344 2539 1186 751 1067 1 1405 2249 1993 591 2006 171 663 2384 701 110 3347 1662 1021 1899 11 4126 2523 3034 1166 25 703 3043 2441 1118 2606 484 697 2463 547 1263 2836 614 329 503 1673 1730 3102 975 2071 1696 2247 36 338 940 452 894 271 2429 1842 2219 1594 321 1687 2595 553 272 435 1378 3417 1014 2873 400 2551 1639 1436 2799 2434 3731 2535 2188 376 2604 2648 2297 2231 579 323 51 1821 87 1133 1428 100 1438 1820 2546 1247 1450 2012 567 1877 1793 804 348 380 2690 2261 317 2005 2481 2526 2724 1071 1277 1280 1874 644 363 1769 848 1597 2398 977 398 1043 2937 1826 2715 20 85 236 1895 2133 479 573 2734 208 1967 2636 928 1307 2707 2980 2189 1318 1873 2198 1879 2813 2170 485 2569 232 896 3650 2581 2064 1058 3356 732 1105 3158 2536 1568 223
Output: ?
To be frank, the first three challenges were bait. This is the one that I wanted to share. It can be solved in pseudo-polynomial time, and the sum of the digits of the correct output is 23.
Feel free to comment.
Some time has passed since I posted this. Here is a Python solution:
def TheEasiestHardestProblem(a):
b = {0}
for c in a: b |= {c + d for d in b}
return sum(a) - min(abs(sum(a) - 2 * c) for c in b)