My fellow Adiyat in our company POLATIC bug me with this question “How to counting number contain 14 in 10 millions numbers less than 1 second?”. Then I thought, it’s easy, let give python a shot!
1 | print len([x for x in range(0, 10000000) if str(x).find(’14’) > -1]) |
With result “590040” it’s takes 9.6s based on SublimeText (yes, i’m kindda hipster guy!). This is not good, no one want to waiting around 10 seconds to get the answer!
Lets break it down by printing sample data for 0-100 and 0-1000
1 2 | print [x for x in range(0, 100) if str(x).find(’14’) > -1] print [x for x in range(0, 1000) if str(x).find(’14’) > -1] |
And we got :
1 2 3 | [14] [114, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 214, 314, 414, 514, 614, 714, 814, 914] [Finished in 0.2s] |
Wait, i want more, this is not enough to see pattern
1 2 3 4 | [14] [114, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 214, 314, 414, 514, 614, 714, 814, 914] [1014, 1114, 1140, 1141, 1142, 1143, 1144, 1145, 1146, 1147, 1148, 1149, 1214, 1314, 1400, 1401, 1402, 1403, 1404, 1405, 1406, 1407, 1408, 1409, 1410, 1411, 1412, 1413, 1414, 1415, 1416, 1417, 1418, 1419, 1420, 1421, 1422, 1423, 1424, 1425, 1426, 1427, 1428, 1429, 1430, 1431, 1432, 1433, 1434, 1435, 1436, 1437, 1438, 1439, 1440, 1441, 1442, 1443, 1444, 1445, 1446, 1447, 1448, 1449, 1450, 1451, 1452, 1453, 1454, 1455, 1456, 1457, 1458, 1459, 1460, 1461, 1462, 1463, 1464, 1465, 1466, 1467, 1468, 1469, 1470, 1471, 1472, 1473, 1474, 1475, 1476, 1477, 1478, 1479, 1480, 1481, 1482, 1483, 1484, 1485, 1486, 1487, 1488, 1489, 1490, 1491, 1492, 1493, 1494, 1495, 1496, 1497, 1498, 1499, 1514, 1614, 1714, 1814, 1914, 2014, 2114, 2140, 2141, 2142, 2143, 2144, 2145, 2146, 2147, 2148, 2149, 2214, 2314, 2414, 2514, 2614, 2714, 2814, 2914, 3014, 3114, 3140, 3141, 3142, 3143, 3144, 3145, 3146, 3147, 3148, 3149, 3214, 3314, 3414, 3514, 3614, 3714, 3814, 3914, 4014, 4114, 4140, 4141, 4142, 4143, 4144, 4145, 4146, 4147, 4148, 4149, 4214, 4314, 4414, 4514, 4614, 4714, 4814, 4914, 5014, 5114, 5140, 5141, 5142, 5143, 5144, 5145, 5146, 5147, 5148, 5149, 5214, 5314, 5414, 5514, 5614, 5714, 5814, 5914, 6014, 6114, 6140, 6141, 6142, 6143, 6144, 6145, 6146, 6147, 6148, 6149, 6214, 6314, 6414, 6514, 6614, 6714, 6814, 6914, 7014, 7114, 7140, 7141, 7142, 7143, 7144, 7145, 7146, 7147, 7148, 7149, 7214, 7314, 7414, 7514, 7614, 7714, 7814, 7914, 8014, 8114, 8140, 8141, 8142, 8143, 8144, 8145, 8146, 8147, 8148, 8149, 8214, 8314, 8414, 8514, 8614, 8714, 8814, 8914, 9014, 9114, 9140, 9141, 9142, 9143, 9144, 9145, 9146, 9147, 9148, 9149, 9214, 9314, 9414, 9514, 9614, 9714, 9814, 9914] [Finished in 0.2s] |
Did you see the patterns?
1 2 3 | [{1 number}] [{1 number}, 140..{10 number}, {1 number}, {1 number}, {1 number}, {1 number}, {1 number}, {1 number}, {1 number}, {1 number}] [{1 number}, {1 number},{10 number}, {3 number} {100 number}, {5 number}, 2014, 2114, {10 number}, 2214, 2314, 2414, 2514, 2614, 2714, 2814, 2914, 3014, 3114, {10 number}, 3214, 3314, 3414, 3514, 3614, 3714, 3814, 3914, 4014, 4114, {10 number}, …] |
Which i can convert into simple list like :
1 2 3 | 1 9 + 10, … => total (19) + 1 = 20 9 + 10, 100, 10 + 10, 10 + 10, 10 + 10, 10 + 10 … => total (279) + 20 = 299 |
My assumption, we need (10^n-2) here to capture total number in combination 14, 14x, 14xx, 14xxx … so on.
Second, we see need for recursive function to add result from previous base.
1 | f(x) = 10 * f(n-1) + 10^n-2 |
Let do test with base 2, 3 and 4 on paper :
1 2 3 | 1 10 + 10 100 + 200 |
Well, it’s failed on base 3. Let’s think that this formula 10 * f(n-1) missing reduce duplicate number. Let’s reduce it with f(n-2) and recalculate again :
1 2 3 | 1 10 + 10 100 + 199 |
Yeay! Let’s write into code :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | """ Calculate contain number of whatever base 2 number in given base number """ def counting(n): if n == 2: return 1 elif n < 2: return 0 return 10 * counting(n-1) – counting(n-2) + 10**(n-2) if __name__ == "__main__": n = 7 print "The results counting {} base is {}".format(n, counting(n)) |
And the results is :
1 2 | The results counting 7 base is 590040 [Finished in 0.2s] |
In Polatic, we always learn and solve enterprise problems with best approach. See pattern and use algorithm to provide quick solution is one of our daily challenge.
Btw, you can check my github in http://github.com/yodiaditya or our company github http://github.com/polatic
Follow this discussion in HackerNews:
https://news.ycombinator.com/item?id=9165357